Cycle index for $S_2\times S_4$

Question

I am trying to determine the cycle index polynomial of $S_2\times S_4$, for the purpose of finding colourings. This is what I have tried:

I computed the polynomials for $S_2$ and $S_4$:

$$Z_{S_4}(t_1,\dots ,t_4)=\frac{1}{4!}\left(6t_4^1+8t_3^1t_1^1+3t_2^2+6t_2^1t_1^2+t_1^4\right)$$

$$Z_{S_2}(s_1,s_2)=\frac{1}{2!}\left(s_1^2+s_2^1\right)$$ where $t_i^k$ indicates the presence of $k$ cycles of length $i$ in some cycle class. From what I can see, 'multiplying' should be done using an operation $\cdot$ likewise: $$t_i^n \cdot s_j^m = w_{\text{lcm}(i,j)}^{mn\cdot\text{gcd(i,j)}}$$ where $w_k$ are variables for $Z_{S_2\times S_4}$, and if there are several variables as a product (e.g. $t_3^1 t_1^1$) then multiplying by something else, we do pairs separately and multiply, for instance: $$t_3^1t_1^1\cdot s_1^2=(t_3^1 \cdot s_1^2)(t_1^1\cdot s_1^2)=w_3^2w_1^2$$ Applying this to the product of both polynomials I get:

$$Z_{S_2}(s_1,s_2)\cdot Z_{S_4}(t_1,\dots,t_4)=\boxed{\frac{1}{48}\left(w_1^8 + 6 w_1^4 w_2^2 + 13 w_2^4 + 8 w_1^2 w_3^2 + 8 w_2 w_6 + 12 w_4^2\right)}$$

Correction I miscalculated so have updated. As mentioned in a comment below, I interpreted the technique as, if I set all the $w_i$ to $C$, then letting $C=$ some number of colors, giving:

$$Z_{S_2\times S_4}(C,\dots,C)= \frac{1}{48}\left(C^8 + 6C^6+21C^4+ 20C^2\right) $$

This should evaluate to the number of colorings of $2\times 4$ tiles, up to row and column permutation. It works for $C=2,3$ (we get $22, 267$) but fails at $C=4$ where I get $1996$ instead of $1870$.

Would love it if someone could point me in the right direction. Trying to teach myself and I think I've misunderstood how this is meant to work...

Answer 1

In trying to compute $Z(S_2\times S_4)$ we use the two possibilities from

$$Z(S_2) = \frac{1}{2} (s_1^2 + s_2^1).$$

We also have

$$Z(S_4) = \frac{1}{24} (t_1^4 + 6 t_1^2 t_2 + 8 t_1 t_3 + 3 t_2^2 + 6 t_4).$$

Now to compute the product of $s_p^n$ and $t_q^m$ we consider two cycles of length $p$ and $q.$ These yield $p\times q$ pairs and we seek the factorization into cycles of the joint action on these pairs of $s_p$ and $t_q$, with $s_p$ acting on the first component of the pair and $t_q$ the second. The order of such a pair is $\mathrm{LCM}(p,q)$ which divides the $pq$ pairs into $pq/\mathrm{LCM}(p,q) = \mathrm{GCD}(p,q)$ cycles. For the first cycle we have $n$ possibilities and for the second, $m$ possibilities, for a total of $m \times n$ pairs of cycles $s_p$ and $t_q.$ Therefore the product operation is given by

$$s_p^n \cdot t_q^m = a_{\mathrm{LCM}(p,q)}^{mn\times \mathrm{GCD}(p,q)}.$$

Now for $s_1^2$ we are fixing the two rows of the board and permuting the columns, hence it suffices to square terms from $Z(S_4)$ to get

$$\frac{1}{48} (a_1^8 + 6 a_1^4 a_2^2 + 8 a_1^2 a_3^2 + 3 a_2^4 + 6 a_4^2).$$

For $s_2$ we have the rule that pairing with $t_q$ (we have $2q$ pairs) where $q$ is odd has order $2q$ and hence yields $a_{2q}$, and order $q$ when $q$ is even and hence yields $a_q^2$. Processing these in sequence we obtain

• $t_1^4$: $q=1$, total is $a_2^4$
• $6 t_1^2 t_2$: $q=1$, $a_2^2$ and $q=2$, $a_2^2$, total is $6 a_2^4.$
• $8 t_1 t_3$: $q=1$, $a_2$ and $q=3$, $a_6$, total is $8 a_2 a_6$
• $3 t_2^2$: $q=2$, $a_2^2$, total is $3 a_2^4$
• $6 t_4$: $q=4$, total is $6 a_4^2.$

This contribution is

$$\frac{1}{48} (10 a_2^4 + 8 a_2 a_6 + 6 a_4^2).$$

Collecting the two pieces we get

$$\bbox[5px,border:2px solid #00A000]{ Z(S_2 \times S_4) = \frac{1}{48} (a_1^8 + 6 a_1^4 a_2^2 + 8 a_1^2 a_3^2 + 13 a_2^4 + 8 a_2 a_6 + 12 a_4^2).}$$

We normally would not do this computation with pen and paper but use a CAS instead. With Maple as shown below we can treat the case of a $2\times N$ board and get e.g. for $N=6:$

$$Z(S_2\times S_6) = {\frac {{a_{{1}}}^{12}}{1440}}+{\frac {{a_{{1}}}^{8}{a _{{2}}}^{2}}{96}}+1/36\,{a_{{1}}}^{6}{a_{{3}}}^{2}+1/ 32\,{a_{{1}}}^{4}{a_{{2}}}^{4}\\+1/16\,{a_{{1}}}^{4}{a_{ {4}}}^{2}+1/12\,{a_{{1}}}^{2}{a_{{2}}}^{2}{a_{{3}}}^{2 }+{\frac {91\,{a_{{2}}}^{6}}{1440}}+1/10\,{a_{{1}}}^{2 }{a_{{5}}}^{2}\\+1/9\,{a_{{2}}}^{3}a_{{6}}+3/16\,{a_{{2} }}^{2}{a_{{4}}}^{2}+1/36\,{a_{{3}}}^{4}+1/10\,a_{{2}}a _{{10}}+{\frac {7\,{a_{{6}}}^{2}}{36}}.$$

We obtain for two colors with a $2\times N$ board the following sequence of inequivalent colorings:

$$3, 7, 13, 22, 34, 50, 70, 95, 125, 161, \ldots$$

which points us to OEIS A002623 where the problem statement by OP is cited as a definition of the sequence, so we have the correct result.

The Maple code for this goes as follows:

with(combinat);

pet_cycleind_symm :=
proc(n)
local l;
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_cycleind_board2N :=
proc(N)
option remember;
local sidx, idx, sl, q;

    sidx := pet_cycleind_symm(N);

    sl := [seq(a[q]=a[q]^2, q=1..N)];
    idx := 1/2*subs(sl, sidx);

    sl := [seq(`if`(type(q, odd),
                    a[q] = a[2*q],
                    a[q] = a[q]^2),
               q=1..N)];
    idx + 1/2*subs(sl, sidx);
end;

Q :=
proc(N, C)
option remember;
local sl, q;

    sl := [seq(a[q] = C, q=1..2*N)];
    subs(sl, pet_cycleind_board2N(N));
end;

Note that we can compute a closed form of the count of colorings using a $2\times N$ board and $C$ colors with the exponential formula which gives the OGF of the cycle index $Z(S_N)$ of the symmetric group. The formula states

$$Z(S_N) = [w^N] \exp\left(\sum_{\ell\ge 1} a_\ell \frac{w^\ell}{\ell}\right).$$

Now for the first term we square the $a_\ell$ and replace by the count $C$ of the number of colors to get

$$\frac{1}{2} [w^N] \exp\left(\sum_{\ell\ge 1} C^2 \frac{w^\ell}{\ell}\right) = \frac{1}{2} [w^N] \exp\left(C^2 \log\frac{1}{1-w}\right) \\ = \frac{1}{2} [w^N] \frac{1}{(1-w)^{C^2}} = \frac{1}{2} {N + C^2-1\choose N}.$$

For the second term we double the length of odd cycles and square even ones:

$$\frac{1}{2} [w^N] \exp\left(\sum_{\ell\ge 1} a_{2\ell}^2 \frac{w^{2\ell}}{2\ell} + \sum_{\ell\ge 0} a_{4\ell+2} \frac{w^{2\ell+1}}{2\ell+1}\right) \\ = \frac{1}{2} [w^N] \exp\left(\sum_{\ell\ge 1} C^2 \frac{w^{2\ell}}{2\ell} + \sum_{\ell\ge 0} C \frac{w^{2\ell+1}}{2\ell+1}\right) \\ = \frac{1}{2} [w^N] \frac{1}{(1-w^2)^{C^2/2}} \exp\left(C \sum_{\ell\ge 0} \frac{w^{\ell}}{\ell} - C \sum_{\ell\ge 0} \frac{w^{2\ell}}{2\ell} \right) \\ = \frac{1}{2} [w^N] \frac{1}{(1-w^2)^{C^2/2}} \frac{1}{(1-w)^C} (1-w^2)^{C/2} \\ = \frac{1}{2} [w^N] \frac{1}{(1-w^2)^{C(C-1)/2}} \frac{1}{(1-w)^C}.$$

Collecting the two pieces we get the following closed form:

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2} [w^N] \left[ \frac{1}{(1-w)^{C^2}} + \frac{1}{(1+w)^{C(C-1)/2}} \frac{1}{(1-w)^{C(C+1)/2}} \right].}$$

Extracting coefficients yields

$$\bbox[5px,border:2px solid #00A000]{ \begin{gather} \frac{1}{2} {N + C^2-1\choose N} \\ + \frac{1}{2} \sum_{q=0}^N {C(C-1)/2-1+q\choose q} \times (-1)^q \times {C(C+1)/2-1+N-q\choose N-q}. \end{gather}}$$

We get in particular for two colors the generating function is the following:

$$\frac{1}{2} \frac{1}{(1-w)^4} + \frac{1}{2} \frac{1}{(1+w)(1-w)^3} \\ = \frac{1}{2} \frac{1+w}{(1+w)(1-w)^4} + \frac{1}{2} \frac{1-w}{(1+w)(1-w)^4} = \frac{1}{(1+w)(1-w)^4}.$$

Converting to partial fractions, we get

$$\frac{1}{16}\frac{1}{1+w} + \frac{1}{16}\frac{1}{1-w} + \frac{1}{8}\frac{1}{(1-w)^2} + \frac{1}{4}\frac{1}{(1-w)^3} + \frac{1}{2}\frac{1}{(1-w)^4}.$$

Extracting the coefficient we have

$$\frac{1}{16} (-1)^N + \frac{1}{16} + \frac{1}{8} {N+1\choose 1} + \frac{1}{4} {N+2\choose 2} + \frac{1}{2} {N+3\choose 3}$$

for a total of

$$\frac{1}{12} N^3 + \frac{5}{8} N^2 + \frac{17}{12} N + \frac{(-1)^N}{16} + \frac{15}{16}.$$