# 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. Nov 21, 2015 at 4:02
• Said another way, the terms on the RHS describe probabilities that a permutation in $S_n$ has some cycle type. Nov 21, 2015 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).$$ Nov 21, 2015 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_{\sum ic_i = n} \prod_{i=1}^n \frac{z_i^{c_i}}{i^{c_i} c_i!}$$

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.