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 which are the sum of the -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 will be used to represent 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 -th complete homogeneous symmetric function expressed in terms of power sum symmetric functions.
The operation elementary computes the -th elementary symmetric function for argument n.
The operation alternating returns the cycle index of the alternating group having an even number of even parts in each cycle partition.
The operation cyclic returns the cycle index of the cyclic group.
The operation dihedral is the cycle index of the dihedral group.
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.
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.
For example,
This integer is the number of different sets of four pairs no two pairs being equal.
For example,
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.
Here it is again, but with no equal pairs.
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.
The cycle index of vertices of a square is dihedral 4.
The number of different squares with 2 red vertices and 2 blue vertices.
The number of necklaces with 3 red beads, 2 blue beads and 2 green beads.
The number of graphs with 5 nodes and 7 edges.
The cycle index of rotations of vertices of a cube.
The number of cubes with 4 red vertices and 4 blue vertices.
The number of labeled graphs with degree sequence 2 2 2 1 1 with no loops or multiple edges.
Again, but with loops allowed but not multiple edges.
Again, but with multiple edges allowed, but not loops
Again, but with both multiple edges and loops allowed
Having constructed a cycle index for a configuration we are at liberty to evaluate the 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 , and then evaluating eval(f, cycleindex).
For the integers 0 and 1, or two colors.
For the integers 0, 1, 2, ... we have this.
The coefficient of 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:
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:
and now we can use it:
The coefficient of is the number of necklaces with n red beads and n-8 green beads.
The coefficient of is the number of partitions of n into 4 or fewer parts.
The coefficient of is the number of partitions of n into 4 boxes containing ordered distinct parts.
The coefficient of is the number of different cubes with n red vertices and 8-n green ones.
The coefficient of is the number of different cubes with integers on the vertices whose sum is n.
The coefficient of 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.
Graphs with 15 nodes enumerated with respect to number of edges.
Necklaces with 7 green beads, 8 white beads, 5 yellow beads and 10 red beads.
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.
This is the number filled with a a b b c c d d.
The configurations enumerated above are:
This is the number of tableaux filled with 1..8.
The coefficient of is the number of column strict reverse plane partitions of n of shape 3 2 2 1.
The smallest is