Substitutions into cycle indices

#### Substitutions into cycle indices

Following Pólyas theorem the numbers of G-orbits of functions fÎYX 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 xi in `a` by 1+zi, where xi and z are indeterminates. In the second case each variable xi of the cycle index `a` is replaced by åj=1`b` zji. 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 xi in the cycle index `a` by 1+2zi. `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 xi in the cycle index `a` (a POLYNOM object) by 1+ixi. `c` is the number of variables in `a`, and `c` is the result after the substitution.

Sometimes it is necessary to replace xi by a series

ån=0¥ xni.
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 xj(i) in the i-th family of the cycle index is replaced by 1+yij. 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