<s>[INST] 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.
 [/INST] $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.
</s>