====================================================================
CycleIndicators examples
====================================================================

This section is based upon the paper J. H. Redfield, ``The Theory of
Group-Reduced Distributions'', 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 application of
symmetric functions and Hammond operators to combinatorial theory.

The theory is based upon the power sum symmetric functions s(i) which
are the sum of the i-th 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 n is a collection of positive integers called
its parts whose sum is n.  For example, the partition (3^2 2 1^2) will
be used to represent s^2_3 s_2 s^2_1 and will indicate that the
permutation has two cycles of length 3, 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.

The operation complete returns the cycle index of the symmetric group
of order n for argument n.  Alternatively, it is the n-th complete
homogeneous symmetric function expressed in terms of power sum
symmetric functions.

  complete 1
   (1)
                      Type: SymmetricPolynomial Fraction Integer

  complete 2
   1       1   2
   - (2) + - (1 )
   2       2
                      Type: SymmetricPolynomial Fraction Integer

  complete 3
   1       1         1   3
   - (3) + - (2 1) + - (1 )
   3       2         6
                      Type: SymmetricPolynomial Fraction Integer

  complete 7
     1       1          1          1     2     1         1            1     3
     - (7) + - (6 1) + -- (5 2) + -- (5 1 ) + -- (4 3) + - (4 2 1) + -- (4 1 )
     7       6         10         10          12         8           24
   + 
      1   2      1     2     1       2     1     4     1   3      1   2 3
     -- (3 1) + -- (3 2 ) + -- (3 2 1 ) + -- (3 1 ) + -- (2 1) + -- (2 1 )
     18         24          12            72          48         48
   + 
      1      5      1    7
     --- (2 1 ) + ---- (1 )
     240          5040
                   Type: SymmetricPolynomial Fraction Integer

The operation elementary computes the n-th elementary symmetric
function for argument n.

  elementary 7
     1       1          1          1     2     1         1            1     3
     - (7) - - (6 1) - -- (5 2) + -- (5 1 ) - -- (4 3) + - (4 2 1) - -- (4 1 )
     7       6         10         10          12         8           24
   + 
      1   2      1     2     1       2     1     4     1   3      1   2 3
     -- (3 1) + -- (3 2 ) - -- (3 2 1 ) + -- (3 1 ) - -- (2 1) + -- (2 1 )
     18         24          12            72          48         48
   + 
        1      5      1    7
     - --- (2 1 ) + ---- (1 )
       240          5040
                  Type: SymmetricPolynomial Fraction Integer

The operation alternating returns the cycle index of the alternating 
group having an even number of even parts in each cycle partition.

  alternating 7
     2       1     2    1           1   2      1     2     1     4     1   2 3
     - (7) + - (5 1 ) + - (4 2 1) + - (3 1) + -- (3 2 ) + -- (3 1 ) + -- (2 1 )
     7       5          4           9         12          36          24
   + 
       1    7
     ---- (1 )
     2520
                  Type: SymmetricPolynomial Fraction Integer

The operation cyclic returns the cycle index of the cyclic group.

  cyclic 7
   6       1   7
   - (7) + - (1 )
   7       7
                  Type: SymmetricPolynomial Fraction Integer

The operation dihedral is the cycle index of the dihedral group.

  dihedral 7
   3       1   3      1   7
   - (7) + - (2 1) + -- (1 )
   7       2         14
                  Type: SymmetricPolynomial Fraction Integer

The operation graphs for argument n returns the cycle index of the
group of permutations on the edges of the complete graph with n nodes
induced by applying the symmetric group to the nodes.

  graphs 5
   1           1   2    1   2     1   3     1   4 2     1   3 4     1    10
   - (6 3 1) + - (5 ) + - (4 2) + - (3 1) + - (2 1 ) + -- (2 1 ) + --- (1  )
   6           5        4         6         8          12          120
                  Type: SymmetricPolynomial Fraction Integer

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 cup
of two cycle indices is a kind of scalar product that combines
monomials for permutations with the same cycles.  The cap operation
provides the sum of the coefficients of the result of the cup
operation which will be an integer that enumerates what Redfield
called group-reduced distributions.

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

This integer is the number of different sets of four pairs.

  cap(complete 2**2, complete 2*complete 1**2)
    4
                  Type: Fraction Integer

For example,
  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

This integer is the number of different sets of four pairs no two
pairs being equal.

  cap(elementary 2**2, complete 2*complete 1**2)
    2
                  Type: Fraction Integer

For example,

  a a b b    a a b b
  c d c e    c e c d

In this case the configurations enumerated are easily constructed,
however the theory merely enumerates them providing little help in
actually constructing them.

Here are the number of 6-pairs, first from a a a b b c, second
from d d e e f g.

  cap(complete 3*complete 2*complete 1,complete 2**2*complete 1**2)
    24
                     Type: Fraction Integer

Here it is again, but with no equal pairs.

  cap(elementary 3*elementary 2*elementary 1,complete 2**2*complete 1**2)
    8
                     Type: Fraction Integer

  cap(complete 3*complete 2*complete 1,elementary 2**2*elementary 1**2)
    8
                     Type: Fraction Integer

The number of 6-triples, first from a a a b b c, second from
d d e e f g, third from h h i i j j.

  eval(cup(complete 3*complete 2*complete 1, cup(complete 2**2*complete 1**2,complete 2**3)))
    1500
                     Type: Fraction Integer

The cycle index of vertices of a square is dihedral 4.

  square:=dihedral 4
   1       3   2    1     2    1   4
   - (4) + - (2 ) + - (2 1 ) + - (1 )
   4       8        4          8
                     Type: SymmetricPolynomial Fraction Integer

The number of different squares with 2 red vertices and 2 blue vertices.

  cap(complete 2**2,square)
    2
                     Type: Fraction Integer

The number of necklaces with 3 red beads, 2 blue beads and 2 green beads.

  cap(complete 3*complete 2**2,dihedral 7)
    18
                     Type: Fraction Integer

The number of graphs with 5 nodes and 7 edges.

  cap(graphs 5,complete 7*complete 3)
    4
                     Type: Fraction Integer

The cycle index of rotations of vertices of a cube.

  s(x) == powerSum(x)
                     Type: Void

  cube:=(1/24)*(s 1**8+9*s 2**4 + 8*s 3**2*s 1**2+6*s 4**2)
   1   2    1   2 2    3   4     1   8
   - (4 ) + - (3 1 ) + - (2 ) + -- (1 )
   4        3          8        24
                     Type: SymmetricPolynomial Fraction Integer

The number of cubes with 4 red vertices and 4 blue vertices.

  cap(complete 4**2,cube)
    7
                     Type: Fraction Integer

The number of labeled graphs with degree sequence 2 2 2 1 1 with no 
loops or multiple edges.

  cap(complete 2**3*complete 1**2,wreath(elementary 4,elementary 2))
    7
                     Type: Fraction Integer

Again, but with loops allowed but not multiple edges.

  cap(complete 2**3*complete 1**2,wreath(elementary 4,complete 2))
    17
                     Type: Fraction Integer

Again, but with multiple edges allowed, but not loops

  cap(complete 2**3*complete 1**2,wreath(complete 4,elementary 2))
    10
                     Type: Fraction Integer

Again, but with both multiple edges and loops allowed

  cap(complete 2**3*complete 1**2,wreath(complete 4,complete 2))
    23
                     Type: Fraction Integer

Having constructed a cycle index for a configuration we are at liberty
to evaluate the s_i components any way we please.  For example we can
produce enumerating generating functions.  This is done by providing a
function f on an integer i to the value required of s_i, and then
evaluating eval(f, cycleindex).

  x: ULS(FRAC INT,'x,0) := 'x 
   x
                     Type: UnivariateLaurentSeries(Fraction Integer,x,0)

  ZeroOrOne: INT -> ULS(FRAC INT, 'x, 0) 
                     Type: Void

  Integers: INT -> ULS(FRAC INT, 'x, 0) 
                     Type: Void

For the integers 0 and 1, or two colors.

  ZeroOrOne n == 1+x**n
                     Type: Void

  ZeroOrOne 5 
         5
    1 + x
                     Type: UnivariateLaurentSeries(Fraction Integer,x,0)

For the integers 0, 1, 2, ... we have this.

  Integers n == 1/(1-x**n) 
                     Type: Void

  Integers 5 
         5    10      11
    1 + x  + x   + O(x  )
                     Type: UnivariateLaurentSeries(Fraction Integer,x,0)

The coefficient of x^n is the number of graphs with 5 nodes and n edges. 

Note that there is an eval function that takes two arguments. It has the 
signature:

  ((Integer -> D1),SymmetricPolynomial Fraction Integer) -> D1
    from EvaluateCycleIndicators D1 if D1 has ALGEBRA FRAC INT

This function is not normally exposed (it will not normally be considered
in the list of eval functions) as it is only useful for this particular
domain. To use it we ask that it be considered thus:

  )expose EVALCYC

and now we can use it:

  eval(ZeroOrOne, graphs 5) 
              2     3     4     5     6     7     8    9    10      11
    1 + x + 2x  + 4x  + 6x  + 6x  + 6x  + 4x  + 2x  + x  + x   + O(x  )
                     Type: UnivariateLaurentSeries(Fraction Integer,x,0)

The coefficient of x^n is the number of necklaces with n red beads 
and n-8 green beads.

  eval(ZeroOrOne,dihedral 8) 
              2     3     4     5     6    7    8
    1 + x + 4x  + 5x  + 8x  + 5x  + 4x  + x  + x
                     Type: UnivariateLaurentSeries(Fraction Integer,x,0)

The coefficient of x^n is the number of partitions of n into 4 or fewer parts.

  eval(Integers,complete 4) 
             2     3     4     5     6      7      8      9      10      11
   1 + x + 2x  + 3x  + 5x  + 6x  + 9x  + 11x  + 15x  + 18x  + 23x   + O(x  )
                     Type: UnivariateLaurentSeries(Fraction Integer,x,0)

The coefficient of x^n is the number of partitions of n into 4 boxes
containing ordered distinct parts.

  eval(Integers,elementary 4)
      6    7     8     9     10     11     12      13      14      15      16
     x  + x  + 2x  + 3x  + 5x   + 6x   + 9x   + 11x   + 15x   + 18x   + 23x
   + 
        17
     O(x  )
                     Type: UnivariateLaurentSeries(Fraction Integer,x,0)

The coefficient of x^n is the number of different cubes with n red
vertices and 8-n green ones.

  eval(ZeroOrOne,cube) 
              2     3     4     5     6    7    8
    1 + x + 3x  + 3x  + 7x  + 3x  + 3x  + x  + x
                     Type: UnivariateLaurentSeries(Fraction Integer,x,0)

The coefficient of x^n is the number of different cubes with integers
on the vertices whose sum is n.

  eval(Integers,cube) 
               2     3      4      5      6       7       8       9       10
     1 + x + 4x  + 7x  + 21x  + 37x  + 85x  + 151x  + 292x  + 490x  + 848x
   + 
        11
     O(x  )
                          Type: UnivariateLaurentSeries(Fraction Integer,x,0)

The coefficient of x^n is the number of graphs with 5 nodes and with
integers on the edges whose sum is n.  In other words, the enumeration
is of multigraphs with 5 nodes and n edges.

  eval(Integers,graphs 5) 
               2     3      4      5      6       7       8       9       10
     1 + x + 3x  + 7x  + 17x  + 35x  + 76x  + 149x  + 291x  + 539x  + 974x
   + 
        11
     O(x  )
                     Type: UnivariateLaurentSeries(Fraction Integer,x,0)

Graphs with 15 nodes enumerated with respect to number of edges.

  eval(ZeroOrOne ,graphs 15) 
               2     3      4      5      6       7       8        9        10
     1 + x + 2x  + 5x  + 11x  + 26x  + 68x  + 177x  + 496x  + 1471x  + 4583x
   + 
        11
     O(x  )
                     Type: UnivariateLaurentSeries(Fraction Integer,x,0)

Necklaces with 7 green beads, 8 white beads, 5 yellow beads and 10
red beads.

  cap(dihedral 30,complete 7*complete 8*complete 5*complete 10)
    49958972383320
                     Type: Fraction Integer

The operation 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.

In this case the argument partition represents a tableau shape.  For
example 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.  SFunction [3,2,2,1] counts the number of different tableaux of
shape 3, 2, 2, 1 filled with objects with an ascending order in the
columns and a non-descending order in the rows.

  sf3221:= SFunction [3,2,2,1] 
      1          1     2     1   2     1            1     4     1   2
     -- (6 2) - -- (6 1 ) - -- (4 ) + -- (4 3 1) + -- (4 1 ) - -- (3 2)
     12         12          16        12           24          36
   + 
      1   2 2     1     2      1       3     1     5     1    4     1   3 2
     -- (3 1 ) - -- (3 2 1) - -- (3 2 1 ) - -- (3 1 ) - --- (2 ) + -- (2 1 )
     36          24           36            72          192        48
   + 
      1   2 4     1      6     1    8
     -- (2 1 ) - --- (2 1 ) + --- (1 )
     96          144          576
                     Type: SymmetricPolynomial Fraction Integer

This is the number filled with a a b b c c d d.

  cap(sf3221,complete 2**4) 
    3
                     Type: Fraction Integer

The configurations enumerated above are:

  a a b    a a c    a a d
  b c      b b      b b
  c d      c d      c c
  d        d        d

This is the number of tableaux filled with 1..8.

  cap(sf3221, powerSum 1**8)
    70
                     Type: Fraction Integer

The coefficient of x^n is the number of column strict reverse plane
partitions of n of shape 3 2 2 1.

  eval(Integers, sf3221)
      9     10     11      12      13      14      15       16       17
     x  + 3x   + 7x   + 14x   + 27x   + 47x   + 79x   + 126x   + 196x  
   + 
        18      19      20
    294x  + 432x   + O(x  )
                          Type: UnivariateLaurentSeries(Fraction Integer,x,0)

The smallest is

  0 0 0
  1 1
  2 2
  3

See Also:
o )show CycleIndicators

