# A remarkable sum over partitions

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

• 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. – Lucia Nov 21 '15 at 4:02
• Said another way, the terms on the RHS describe probabilities that a permutation in $S_n$ has some cycle type. – Qiaochu Yuan Nov 21 '15 at 4:17
• Alternatively, equate coefficients of $x^n$ in $$\frac{1}{1-x} = \exp\biggl(\sum_{a=1}^\infty \frac{x^a}{a}\biggr).$$ – Ira Gessel Nov 21 '15 at 6:04

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.