A remarkable sum over partitions

Question

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

Answer 1

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.