| | | **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*^{i}, where
*x*_{i} and *z* are indeterminates.
In the second case each variable *x*_{i} of
the cycle index `a`

is replaced by
*å*_{j=1}^{b} z_{j}^{i}.
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*^{i}.
`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*^{i}.
`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^{ni}.

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}^{(i)} 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@kfunigraz.ac.at,

last changed: November 19, 2001

| | | **Substitutions into cycle indices** |