Cycle Index ExamplesEugene Curtin,  Southwest Texas State Universityemail :   ec01@swt.edu
Copyright:   © 1999 by Eugene Curtin.

0. Initialization.

Needs["`CycleIndices`"]

1. Introduction.

If a  finite group G acts on a finite set S, we associate to each element g of G a monomial m(g)=x[1]^i_1 x[2]^i_2...where g has i_k orbits with k elements. Summing the monomials over G and dividing by |G| yields the cycle index Z(G) of the action of G on S. Many combinatorial questions  can be answered by making substitutions into Z(G). For example setting each x[i]=1 yields the number of orbits of G. Setting x[i]=(1+x^i) yields a polynomial such that the coefficient of x^k will be the number of G-inequivalent k-subsets of S.  The fundamental theorem yielding these combinatorial applications is Polya's Enumeration Theorem. An excellent reference on this material is:
              [HP] Graphical Enumeration, by E. Palmer and F. Harary, Academic Press 1973.
For a  discussion of Polya's Enumeration Theorem see [HP] Chapter 2 Section 4.

2. Some common cycle indices and related  functions.

Monomials[n,x] gives the set of possible cycle-types of elements of a group acting on a set with n elements.

Monomials[5, x]

EvenMonomials gives the monomials corresponding to even permutations.

EvenMonomials[5, x]

The cycle index of some common permutation groups is given in the form GIndex[n,x] where G is the name of the group and n is the number of elements in the set on which G acts. See [HP] Chapter 2 Section 2.

IdentityIndex[10, t]

SymmetricIndex[5, s]

AlternatingIndex[5, w]

DihedralIndex[5, x]

CyclicIndex[5, x]

We may also obtain the cycle index of the centralizer of a symmetric group element given the cycle type of the element.

CentralizerIndex[s[2]^3, s]

We define the inverter of an element g to be the set of permutations h such that  h g (h^(-1))= (g^(-1)).

InverterIndex[s[3]^2, s]

We define the pseudo-centralizer of an element g to be the union of the centralizer and the inverter. 
The pseudo-centralizer of g is a group, but the inverter of g is not unless the order of g is 1 or 2.

PseudoCentralizerIndex[s[2]^2 s[3], s]

3. Enumeration of simple graphs.

One of the sucesses of Polya Theory is the enumeration of simple graphs. Given a cycle index on a set of points,
PairIndex computes the cycle index of the induced action on the set of two-element subsets. The substitution of
(1+x^i) for x[i] in the cycle index of the pair group (the symmetric group with group action on the set of two 
element subsets of {1,2,...,n}) yields a polynomial such that the coefficient of x^k gives the number of non-isomorphic simple graphs on n vertices with k-edges. Further substituting 1 for x yields the total number of graphs with n vertices.
See [HP] Chapter 4 Section 1 for further details.

PairSymmetricIndex[n_, x_] := PairIndex[SymmetricIndex[n, x], x];

Expand[PairSymmetricIndex[5, x] /. {x[i_] -> 1 + x^i}]

% /. {x -> 1}

There are 6 non-isomorphic simple graphs with 5 vertices and 4 edges (6 x^4 term), 34 non-isomorphic simple graphs on 5 vertices.

TableForm[
      Table[{n, PairSymmetricIndex[n, x] /.  {x[i_] -> 2}}, {n, 2, 16}], 
      TableHeadings -> {{}, {"Vertices", "Graphs"}}]

We can easily push things further.

$RecursionLimit = Infinity;

TableForm[
      Table[{n, PairSymmetricIndex[n, x] /.  {x[i_] -> 2}}, {n, 17, 20}], 
      TableHeadings -> {{}, {"Vertices", "Graphs"}}]

4. Some binary operations on cycle indices.

Given the cycle indices ZA and ZB for groups A and B acting on sets X and Y, we can compute the cycle index of the natural actions of AxB on X⋃Y, on X×Y and on Y^X, the set of functions X→Y. These are computed by the functions SumIndex, CrossProductIndex (see [HP] Chapter 4 Section 3) and PowerIndex (see [HP] Chapter 6 Section 1).

\(\(PowerIndex[DihedralIndex[4, x], IdentityIndex[2, x], x]
\)\)

Expand[%  /.  x[i_] -> 1  +  x^i]

The 6x term shows that there are 6 inequivalent ways to 2-color the vertices of the square with two distinguishable colors. 
If we wish to consider the colors themselves as interchangeable, then we obtain 4 different ways:

\(Expand[
      PowerIndex[DihedralIndex[4, x], SymmetricIndex[2, x], x]
 /. 
        x[i_] -> 1\  + \ x^i]\)

Given the cycle indices ZA and ZB for groups A and B acting on sets X and Y, we can compute the cycle index of the natural actions of the wreath product A[B] on X×Y and on Y^X, the set of functions X→Y. These are computed by the functions WreathProductIndex  ([HP], Chapter 4 Section 3) and WreathPowerIndex  ([HP],  Chapter 4 Section 6). The wreath product A[B] of A and B is sometimes refered to as the composition of A and B. The enumeration of bicolored graphs ([HP],  Chapter  4 Section 3) combines the WreathPowerIndex and CrossProductIndex.

\(BicolorPolynomial[n_, m_] := 

      Expand[\((
            If[n == m, 
              WreathPowerIndex[SymmetricIndex[2, x], SymmetricIndex[n, x], 
                x], 
		
              CrossProductIndex[SymmetricIndex[n, x], 
					
                SymmetricIndex[m, x], x]])\) /. {x[i_] -> 1 + \ x^i}]\)

BicolorPolynomial[3, 3]

BicolorPolynomial[3, 2]

The coefficient of x^k gives the in BicolorPolynomial[n,m] gives the number of graphs up to isomorphism with k edges, where the vertices have been divided into a set of n and a set of m of different colors, where no edge is allowed between vertices of the same color. For an application of WreathPowerIndex to counting boolean functions see [HR] Chapter 4 Section 6. The function CentralizerIndex illustrated in  section 2 of this notebook makes use of the WreathProductIndex function.

5. Graph superpositions.  Cup and cap products. J  operator.

See [HP] Chapter 7 for a discussion of graph superpositions, the cup and cap products and the J operator.
Following [HP] Chapter 7 Section 4 we write down the cycle index  ZP of the automorphism group of a path of length 4 and count the number of superpositions of two differently colored copies. CupProduct[ZP,ZP,x] will yield the sum of the cycle-indices of the groups of the different resulting figures and CapProduct[ZP,ZP,x] will count the figures. If the colors are regarded as interchangeable then we use PalmerJIndex (our implementation of the J operator) to obtain the sum of the cycle indices and a substitution into the PalmerJIndex to count the different figures.

ZP = 1/2 (x[1]^4 + x[2]^2);

CupProduct[ZP, ZP, x]

CapProduct[ZP, ZP, x]

PalmerJIndex[ZP, SymmetricIndex[2, x], x]

%  /.  {x[i_] -> 1}

6. Enumeration of Cayley sets in Sn up to conjugation.

We may consider the action of a subgroup G of the symmetric group Sn on the set of permutations with a given set of possible cycle types.

ConjugationIndex[SymmetricIndex[3, x], Monomials[3, x], x]

As cycle-types are preserved under conjugation, we may use a different variable for each cycle-type being acted upon, thereby obtaining a multivariable cycle index. For example,  the x[2,i] terms denote i-cycles of the second element of Monomials[3,x] in the following:

MultiConjugationIndex[SymmetricIndex[3, x], Monomials[3, x], x]

If Xn denotes the equivalence classes of the symmetric group Sn where we put each element and its inverse in an equivalence class, we can consider the conjugation actions on Xn. SkewConjugationIndex and MultiSkewConjugationIndex give the resulting cycle-indeces and multivariable cycle indices. CayleyPolynomial[n,r,s] below has as coefficient of x^r y^s the number of sets in Xn with r elements of order at least 3 and s elements of order 2. It uses the MultiSkewConjugationIndex function and counts undirected Cayley graphs on subgroups of  Sn up to isomorphism induced by conjugation in Sn.

\(\(		

    \(CayleyPolynomial[n_, x_, y_] := 
      Module[
\ \ \ \ \ \ {l = Length[Monomials[n, x]]}, 
\ \ \ \ \ \ 
        MultiSkewConjugationIndex[
\ \ \ \ \ \ \ \ SymmetricIndex[n, x], 
            Monomials[n, x], x]
\ \ \ \ \ \ \ \ \ \ \  /. 
          \ {x[i_, j_] :> 
              Which[i < l - Floor[n/2], 
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 
                1 + x^j, i == l, 1, True, 1 + y^j]}]; \)\)\)

Expand[CayleyPolynomial[4, x, y]]

The following calculations show there are 909 inequivalent 3-regular Cayley graphs in S_8 with generating set one element of order at least 3 and one element of order 2, and 3094 with generating set 3 elements of order 2. These calculations may take a few minutes on slow machines.

XYCoefficient[f_, i_, j_] := 
      1/i! 1/j! D[f, {x, i}, {y, j}] /. {x -> 0, y -> 0}

XYCoefficient[CayleyPolynomial[8, x, y], 1, 1]

XYCoefficient[CayleyPolynomial[8, x, y], 0, 3]