SYMMETRICA-MANUAL -- Substitutions into cycle indices

Substitutions into cycle indices

Substitutions into cycle indices

Following Pólyas theorem the numbers of G-orbits of functions f∈ Y^X where G acts on the domain of these functions can be computed by replacing each variable in the cycle index Z(G,X) by the cardinality of Y.

Here is a list of some possibilities for substitutions into a cycle index. In order to do Pólya enumeration we have:

INT polya_sub(a,b,c)     OP a,b,c;
INT polya_n_sub(a,b,c)   OP a,b,c;

In the first case a is a cycle index, b is the number of variables in a, and c is the result after replacing each variable x_i in a by 1+zⁱ, where x_i and z are indeterminates. In the second case each variable x_i of the cycle index a is replaced by

b
∑
j=1
z_jⁱ.

Therefore b is an INTEGER object; the result is c.

For Pólyas Theorem in constant form one needs

INT polya_const_sub(a,b,c) OP a,b,c;

Each variable of the cycle index a is replaced by the INTEGER object b. The result is c an INTEGER object.

INT polya1_sub(a,b,c)   OP a,b,c;

replaces each variable x_i in the cycle index a by 1+2zⁱ. b is the number of variables in a, and c is the result of this substitution.

The routine

INT polya2_sub(a,c,b) OP a,b,c;

replaces each variable x_i in the cycle index a (a POLYNOM object) by 1+ixⁱ. c is the number of variables in a, and c is the result after the substitution.

Sometimes it is necessary to replace x_i by a series

∞
∑
n=0
xⁿⁱ.

This can be done by

INT co_polya3_sub(a,c,d,b)  OP a,b,c,d;

Again a is a cycle index, c is the number of variables in a and d is the highest power of x that should be substituted. (It is not possible to substitute the complete series yet.) As a matter of fact the result is only correct for all powers of x less than or equal to d. So only these coefficients are computed in b.

For the more dimensional form of Pólyas Theorem there are

INT polya_multi_sub(a,b)          OP a,b;
INT polya_multi_const_sub(a,c,b)  OP a,b,c;

In the first case a is a multi-dimensional cycle index. Each variable x_j⁽ⁱ⁾ in the i-th family of the cycle index is replaced by 1+y_i^j. The result is b a POLYNOM object. Again in the second case a is a multi-dimensional cycle index. c is a VECTOR object, which has an INTEGER entry for each family of indeterminates in a. The variables of the i-th family of the cycle index are replaced by the i-th element of c. The result is b an INTEGER object.

harald.fripertinger "at" uni-graz.at, May 26, 2011

Substitutions into cycle indices