# Cycle index of $S_n \times S_m$

Given $n$, $m$ and $k$, I would like to evaluate cycle index of $S_n \times S_m$ for $c_1 = c_2 = ... = c_{nm} = k$. What is the fastest known algorithm to calculate it? For this particular case, is there any polynomial time algorithm? I know that $Z(S_n) = \frac{1}{n}\sum_{i=1}^na_iZ(S_{n-i})$. Maybe there is a similiar recursive formula for $Z(S_n \times S_m)$?

Edit: For better explanation of the question here I give an example where $n = 2$, $m = 3$, $k = 2$.

$Z(S_2) = \frac{1}{2}(a_1^2 + a_2)$

$Z(S_3) = \frac{1}{6}(b_1^3 + 3b_1b_2 + 2b_3)$

$Z(S_2 \times S_3) = \frac{1}{12} c_1^6 + \frac{1}{3} c_2^3 + \frac{1}{6} c_3^2 + \frac{1}{4} c_1^2 c_2^2 + \frac{1}{6} c_6$

And now substituting $c_1 = c_2 = c_3 = c_4 = c_5 = c_6 = k$ gives $\frac{1}{12} k^6 + \frac{1}{4} k^4 + \frac{1}{3} k^3 + \frac{1}{6} k^2 + \frac{1}{6} k$, so the answer I'm looking for is $13$. Note that I'm interested only in the value, not the polynomial itself.

• Which permutation action of $S_n\times S_m$ are you interested in? If $S_n$ and $S_m$ are acting independently on disjoint sets of sizes $n$ and $m$, then $Z(S_n\times S_m)=Z(S_n)Z(S_m)$. – Richard Stanley Jan 18 '18 at 19:55
• I believe he is using the product action on $[n]\times[m]$. There is a classical paper by Harary on this projecteuclid.org/euclid.pjm/1103039700 – Gjergji Zaimi Jan 18 '18 at 20:23

$Z(S_n \times S_m)$ evaluated at $c_1 = c_2 = ... = c_{nm} = k$ equals $$\sum_{i_1+2i_2+\dots+ni_n=n}\frac{1}{1^{i_1} i_1!\cdots n^{i_n} i_n!} \sum_{j_1+2j_2+\dots+mj_m=m} \frac{1}{1^{j_1} j_1!\cdots m^{j_m} j_m!}\cdot k^{\sum_{p=1}^n\sum_{q=1}^m \gcd(p,q)i_p j_q}.$$ There are $p(n)\cdot p(m)$ terms in this double sum.