path: root/src/hyper/pages/CYCLES.ht

% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\CycleIndicatorsXmpTitle}{CycleIndicators}
\newcommand{\CycleIndicatorsXmpNumber}{9.13}
%
% =====================================================================
\begin{page}{CycleIndicatorsXmpPage}{9.13 CycleIndicators}
% =====================================================================
\beginscroll
This section is based upon the paper
J. H. Redfield, ``The Theory of Group-Reduced Distributions'',
%-% \HDindex{Redfield, J. H.}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
American J. Math.,49 (1927) 433-455,
and is an application of group theory to enumeration problems.
It is a development of the work by P. A. MacMahon on the
%-% \HDindex{MacMahon, P. A.}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
application of symmetric functions and Hammond operators to
%-% \HDindex{function!symmetric}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
combinatorial theory.
%-% \HDindex{operator!Hammond}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
%-% \HDindex{combinatorics}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}

The theory is based upon the power sum symmetric functions
\subscriptIt{s}{i}
which are the sum of the \eth{\it i} powers of the variables.
The cycle index of a permutation is an expression that specifies
the sizes of the cycles of a permutation, and
may be represented as a partition.
A partition of a non-negative integer \spad{n} is a collection
of positive integers called its parts whose sum is \spad{n}.
%-% \HDindex{cycle index}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
For example, the partition
%-% \HDindex{partition}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
\texht{$(3^2 \  2 \ 1^2)$}{\spad{3**2 2 1**2)}}
will be used to represent
\texht{$s^2_3 s_2 s^2_1$}{\spad{(s_3)**2 s_2 (s_1)**2}}
and will indicate that the permutation has two cycles of length 3,
%-% \HDindex{permutation}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
one of length 2 and two of length 1.
The cycle index of a permutation group is the sum of the cycle indices
of its permutations divided by the number of permutations.
The cycle indices of certain groups are provided.
\xtc{
We first expose something from the library.
}{
\spadpaste{)expose EVALCYC}
}
\xtc{
The operation \spadfun{complete} returns the cycle index of the
%-% \HDindex{group!symmetric}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
symmetric group of order \spad{n} for argument \spad{n}.
Alternatively, it is the \eth{\spad{n}} complete homogeneous symmetric
function expressed in terms of power sum symmetric functions.
}{
\spadpaste{complete 1}
}
\xtc{
}{
\spadpaste{complete 2}
}
\xtc{
}{
\spadpaste{complete 3}
}
\xtc{
}{
\spadpaste{complete 7}
}
\xtc{
The operation \spadfun{elementary} computes the \eth{\spad{n}}
elementary symmetric function for argument \spad{n.}
}{
\spadpaste{elementary 7}
}
\xtc{
The operation \spadfun{alternating} returns
%-% \HDindex{group!alternating}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
the cycle index of the alternating group
having an even number of even parts in each cycle partition.
}{
\spadpaste{alternating 7}
}
\xtc{
The operation \spadfun{cyclic} returns the cycle index of the cyclic group.
%-% \HDindex{group!cyclic}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
}{
\spadpaste{cyclic 7}
}
\xtc{
The operation \spadfun{dihedral} is the cycle index of the
%-% \HDindex{group!dihedral}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
dihedral group.
}{
\spadpaste{dihedral 7}
}
\xtc{
The operation \spadfun{graphs} for argument \spad{n} returns
the cycle index of the group of permutations on
the edges of the complete graph with \spad{n} nodes induced by
%-% \HDindex{graph}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
applying the symmetric group to the nodes.
}{
\spadpaste{graphs 5}
}

The cycle index of a direct product of two groups is the product
of the cycle indices of the groups.
Redfield provided two operations on two cycle indices which will
be called ``cup'' and ``cap'' here.
The \spadfun{cup} of two cycle indices is a kind of scalar product
that combines monomials for permutations with the same cycles.
The \spadfun{cap} operation provides the sum of the coefficients
of the result of the \spadfun{cup} operation which will be an
integer that enumerates what Redfield called
group-reduced distributions.

We can, for example, represent  \spad{complete 2 * complete 2}
as the set of objects \spad{a a b b} and
\spad{complete 2 * complete 1 * complete 1} as \spad{c c d e.}

\xtc{
This integer
is the number of different sets of four pairs.
}{
\spadpaste{cap(complete 2**2, complete 2*complete 1**2)}
}
For example,
\begin{verbatim}
a a b b     a a b b    a a b b   a a b b
c c d e     c d c e    c e c d   d e c c
\end{verbatim}

\xtc{
This integer
is the number of different sets of four pairs no two pairs being equal.
}{
\spadpaste{cap(elementary 2**2, complete 2*complete 1**2)}
}
For example,
\begin{verbatim}
a a b b    a a b b
c d c e    c e c d
\end{verbatim}
In this case the configurations enumerated are easily constructed,
however the theory merely enumerates them providing little help in
actually constructing them.
\xtc{
Here are the
number of 6-pairs, first from \spad{a a a b b c,} second from
\spad{d d e e f g.}
}{
\spadpaste{cap(complete 3*complete 2*complete 1,complete 2**2*complete 1**2)}
}
\xtc{
Here it is again, but with no equal pairs.
}{
\spadpaste{cap(elementary 3*elementary 2*elementary 1,complete 2**2*complete 1**2)}
}
\xtc{
}{
\spadpaste{cap(complete 3*complete 2*complete 1,elementary 2**2*elementary 1**2)}
}
\xtc{
The number of 6-triples, first from \spad{a a a b b c,} second from
\spad{d d e e f g,} third from \spad{h h i i j j.}
}{
\spadpaste{eval(cup(complete 3*complete 2*complete 1, cup(complete 2**2*complete 1**2,complete 2**3)))}
}
\xtc{
The cycle index of vertices of a square is dihedral 4.
}{
\spadpaste{square:=dihedral 4}
}
\xtc{
The number of different squares with 2 red vertices and 2 blue vertices.
}{
\spadpaste{cap(complete 2**2,square)}
}
\xtc{
The number of necklaces with 3 red beads, 2 blue beads and 2 green beads.
}{
\spadpaste{cap(complete 3*complete 2**2,dihedral 7)}
}
\xtc{
The number of graphs with 5 nodes and 7 edges.
}{
\spadpaste{cap(graphs 5,complete 7*complete 3)}
}
\xtc{
The cycle index of rotations of vertices of a cube.
}{
\spadpaste{s(x) == powerSum(x)}
}
\xtc{
}{
\spadpaste{cube:=(1/24)*(s 1**8+9*s 2**4 + 8*s 3**2*s 1**2+6*s 4**2)}
}
\xtc{
The number of cubes with 4 red vertices and 4 blue vertices.
}{
\spadpaste{cap(complete 4**2,cube)}
}
\xtc{
The number of labeled graphs with degree sequence \spad{2 2 2 1 1}
with no loops or multiple edges.
}{
\spadpaste{cap(complete 2**3*complete 1**2,wreath(elementary 4,elementary 2))}
}
\xtc{
Again, but
with loops allowed but not multiple edges.
}{
\spadpaste{cap(complete 2**3*complete 1**2,wreath(elementary 4,complete 2))}
}
\xtc{
Again, but
with multiple edges allowed, but not loops
}{
\spadpaste{cap(complete 2**3*complete 1**2,wreath(complete 4,elementary 2))}
}
\xtc{
Again, but
with both multiple edges and loops allowed
}{
\spadpaste{cap(complete 2**3*complete 1**2,wreath(complete 4,complete 2))}
}

Having constructed a cycle index for a configuration
we are at liberty to evaluate the
\subscriptIt{s}{i}
components any way we please.
For example we can produce enumerating generating functions.
%-% \HDindex{function!enumerating generating}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
This is done by providing a function \spad{f} on an integer \spad{i} to the
value required of \subscriptIt{s}{i},
and then evaluating \spad{eval(f, cycleindex)}.
\xtc{
}{
\spadpaste{x: ULS(FRAC INT,'x,0) := 'x \bound{x}}
}
\xtc{
}{
\spadpaste{ZeroOrOne: INT -> ULS(FRAC INT, 'x, 0) \bound{zodec}}
}
\xtc{
}{
\spadpaste{Integers: INT -> ULS(FRAC INT, 'x, 0) \bound{idec}}
}
\xtc{
For the integers 0 and 1, or two colors.
}{
\spadpaste{ZeroOrOne n == 1+x**n \free{x zodec}\bound{zo}}
}
\xtc{
}{
\spadpaste{ZeroOrOne 5 \free{zo}}
}
\xtc{
For the integers \spad{0, 1, 2, ...} we have this.
}{
\spadpaste{Integers n == 1/(1-x**n) \free{x idec}\bound{i}}
}
\xtc{
}{
\spadpaste{Integers 5 \free{i}}
}

\xtc{
The coefficient of \texht{$x^n$}{\spad{x**n}}
is the number of graphs with 5 nodes
and \spad{n} edges.
}{
\spadpaste{eval(ZeroOrOne, graphs 5) \free{zo}}
}
\xtc{
The coefficient of \texht{$x^n$}{\spad{x**n}}  is the number of necklaces with
\spad{n} red beads and \spad{n-8} green beads.
}{
\spadpaste{eval(ZeroOrOne,dihedral 8) \free{zo}}
}
\xtc{
The coefficient of \texht{$x^n$}{\spad{x**n}} is the number of partitions of
\spad{n} into 4 or fewer parts.
}{
\spadpaste{eval(Integers,complete 4) \free{i}}
}
\xtc{
The coefficient of \texht{$x^n$}{\spad{x**n}} is the number of
partitions of \spad{n} into 4
boxes containing ordered distinct parts.
}{
\spadpaste{eval(Integers,elementary 4) \free{i}}
}
\xtc{
The coefficient of \texht{$x^n$}{\spad{x**n}} is the number of
different cubes with \spad{n} red vertices and \spad{8-n} green ones.
}{
\spadpaste{eval(ZeroOrOne,cube) \free{zo}}
}
\xtc{
The coefficient of \texht{$x^n$}{\spad{x**n}} is the number of different cubes with integers
on the vertices whose sum is \spad{n.}
}{
\spadpaste{eval(Integers,cube) \free{i}}
}
\xtc{
The coefficient of \texht{$x^n$}{\spad{x**n}} is the number of
graphs with 5 nodes and with integers on the edges whose sum is
\spad{n.}
In other words, the enumeration is of multigraphs with 5 nodes and
\spad{n} edges.
}{
\spadpaste{eval(Integers,graphs 5) \free{i}}
}
\xtc{
Graphs with 15 nodes enumerated with respect to number of edges.
}{
\spadpaste{eval(ZeroOrOne ,graphs 15) \free{zo}}
}
\xtc{
Necklaces with 7 green beads, 8 white beads, 5 yellow beads and 10
red beads.
}{
\spadpaste{cap(dihedral 30,complete 7*complete 8*complete 5*complete 10)}
}
The operation \spadfun{SFunction} is the S-function or Schur function
of a partition written
as a descending list of integers expressed in terms of power sum
symmetric functions.
\xtc{
In this case the argument partition represents a tableau shape.
For example \spad{3,2,2,1} represents a tableau with three boxes in the
first row, two boxes in the second and third rows, and one box in the
fourth row.
\spad{SFunction [3,2,2,1]}
counts the number of different tableaux of shape \spad{3, 2, 2, 1} filled
with objects with an ascending order in the columns and a
non-descending order in the rows.
}{
\spadpaste{sf3221:= SFunction [3,2,2,1] \bound{sf3221}}
}
\xtc{
This is the number filled with \spad{a a b b c c d d.}
}{
\spadpaste{cap(sf3221,complete 2**4) \free{sf3221}}
}
The configurations enumerated above are:
\begin{verbatim}
a a b    a a c    a a d
b c      b b      b b
c d      c d      c c
d        d        d
\end{verbatim}
\xtc{
This is the number of tableaux filled with \spad{1..8.}
%-% \HDindex{tableaux}{CycleIndicatorsXmpPage}{9.13}{CycleIndicators}
}{
\spadpaste{cap(sf3221, powerSum 1**8)\free{sf3221}}
}
\xtc{
The coefficient of \texht{$x^n$}{\spad{x**n}} is the number
of column strict reverse plane partitions of \spad{n} of shape
\spad{3 2 2 1.}
}{
\spadpaste{eval(Integers, sf3221)\free{i sf3221}}
}
The smallest is
\begin{verbatim}
0 0 0
1 1
2 2
3
\end{verbatim}
\endscroll
\autobuttons
\end{page}
%