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$
2
  • $\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$ Jan 18, 2018 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$ Jan 18, 2018 at 20:23

1 Answer 1

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$
2
  • $\begingroup$ Can it be further simplified or transformed in order not to generate all partitions? $\endgroup$ Jan 19, 2018 at 16:12
  • $\begingroup$ @user128409235: I doubt so. $\endgroup$ Jan 20, 2018 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.