5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Richard Stanley Jan 18 '18 at 19:55
  • $\begingroup$ 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 $\endgroup$ – Gjergji Zaimi Jan 18 '18 at 20:23
1
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ Can it be further simplified or transformed in order not to generate all partitions? $\endgroup$ – user128409235 Jan 19 '18 at 16:12
  • $\begingroup$ @user128409235: I doubt so. $\endgroup$ – Max Alekseyev Jan 20 '18 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.