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

Improve this question
$\endgroup$
3
  • 16
    $\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$ Commented Nov 21, 2015 at 4:02
  • 5
    $\begingroup$ Said another way, the terms on the RHS describe probabilities that a permutation in $S_n$ has some cycle type. $\endgroup$ Commented Nov 21, 2015 at 4:17
  • 7
    $\begingroup$ Alternatively, equate coefficients of $x^n$ in $$\frac{1}{1-x} = \exp\biggl(\sum_{a=1}^\infty \frac{x^a}{a}\biggr).$$ $\endgroup$ Commented Nov 21, 2015 at 6:04

1 Answer 1

Reset to default
15
$\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_{\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.