7
$\begingroup$

While studying some seemingly unrelated topological questions, I have experimentally discovered what appears (to me) to be a remarkable sum over partitions. I was wondering if anyone knows how to prove it.

Fixing $n \geq 1$, it can be stated as follows:

$$1=\sum_{(a_1^{k_1},\ldots,a_p^{k_p}) \vdash n} \left(\frac{1}{(a_1^{k_1}) (k_1 !)}\right) \left(\frac{1}{(a_2^{k_2}) (k_2 !)}\right)\cdots\left(\frac{1}{(a_p^{k_p}) (k_p !)}\right).$$ Here the sum is over all unordered partitions of $n$, and the symbol $(a_1^{k_1},\ldots,a_p^{k_p})$ denotes the partition where $a_1$ appears $k_1 \geq 1$ times, where $a_2$ appears $k_2 \geq 1$ times, etc, and where $a_1 > a_2 > \cdots > a_p > 0$.

I have numerically verified this up to $n=6$.

$\endgroup$
  • 13
    $\begingroup$ If you multiply both sides by $n!$ the LHS is the total number of permutations in $S_n$ and the RHS counts those with a given cycle structure $k_1$ cycles of length $a_1$, etc. $\endgroup$ – Lucia Nov 21 '15 at 4:02
  • 4
    $\begingroup$ Said another way, the terms on the RHS describe probabilities that a permutation in $S_n$ has some cycle type. $\endgroup$ – Qiaochu Yuan Nov 21 '15 at 4:17
  • 5
    $\begingroup$ Alternatively, equate coefficients of $x^n$ in $$\frac{1}{1-x} = \exp\biggl(\sum_{a=1}^\infty \frac{x^a}{a}\biggr).$$ $\endgroup$ – Ira Gessel Nov 21 '15 at 6:04
12
$\begingroup$

Here is a more informative version of this identity. Let $Z_n$ denote the cycle index polynomial of the symmetric group $S_n$, namely

$$Z_n = \frac{1}{n!} \sum_{\sigma \in S_n} z_1^{c_1(\sigma)} z_2^{c_2(\sigma)} \dots $$

where $c_i(\sigma)$ denotes the number of $i$-cycles of $\sigma$. The observations in the comments boil down to the observation that

$$Z_n = \sum_{\lambda \vdash n} \frac{z_1^{\lambda_1} z_2^{\lambda_2} \dots}{1^{\lambda_1} \lambda_1! 2^{\lambda_2} \lambda_2! \dots }$$

and setting all $z_i = 1$ gives your identity, but without doing this, it is possible to arrange the $Z_n$ into a beautiful generating function, namely

$$\sum_{n \ge 0} Z_n t^n = \exp \left( \sum_{n \ge 1} \frac{z_i t^i}{i} \right).$$

This is the "permutation form" of the exponential formula, which has many applications in combinatorics. See, for example, Stanley's Enumerative Combinatorics: Volume 2 for an exposition, or this blog post.

$\endgroup$

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.