# how interpret this partition identity?

use the symbol $P(N)$ to denote the set of all partitions of a positive integer $N$ and denote by $P_k$ the number of occurrences of $k$ in the partition $P \in P(N)$, so that $$N = \sum kP_k$$

by equating coefficients in the identity: $$\frac1{1-x} = e^{-\ln(1-x)}=e^{\sum_{k=1}^{\infty}\frac{x^k}{k}}$$ we see that $$\sum_{P \in P(N)}\left( \prod_{P_k\gt 0}k^{P_k}P_k!\right)^{-1} = 1 \tag{1}$$ Question (a) does this identity have any well-known combinatorial interpretation? (b) is there a simple direct proof of (1) which does not invoke power series?

• just mean the usual partitions. i will try to improve the wording later, or perhaps you could edit it? – David Holden Jan 17 '15 at 11:41
• @bof made some changes. is it clearer now? – David Holden Jan 17 '15 at 12:55

## 2 Answers

hint: look at http://lipn.univ-paris13.fr/~duchamp/Books&more/Macdonald/%5BI._G._Macdonald%5D_Symmetric_Functions_and_Hall_Pol%28BookFi.org%29.pdf pg 24 (2.14) giving the $z_\lambda$ ; your expression is $z_\lambda/n!$ known as the inverses of the class sizes of the symmetric group $S_n$.
Example: for $S_5$ we get class sizes 24, 30, 20, 20, 15, 10, 1 adding to $5!$ or 120 (order of the group). Divide them by $5!$ and the sum gets to be 1.

• thanks very much for that link. – David Holden Jan 17 '15 at 13:27

When we break a given permutation in $S_n$ into a product of disjoint cycles we obtain a partition of $n$. As you have defined, let $P_k$ be the number of cycles of length $k$ in such a cycle decomposition. Define the type of a permutation to be the vector $P = (P_1, P_2, ..., P_n)$. Note the bijection between types and partitions. Let's count $C_P$, the number of permutations of type $P$. First we pick the elements in each cycle. The number of ways to do this is the multinomial

$${n \choose 1...1 \; 2...2 \; ... \; k...k \; ...} = \frac{n!}{\prod k!^{P_k}}$$

Each cycle with k elements can then be arranged in $(k-1)!$ ways, so we multiply the above by

$$\prod (k-1)!^{P_k}$$

And finally, since each set of $k$-cycles can be ordered in $P_k!$ ways, we notice that we overcount by

$$\prod P_k!$$

Putting all these together we find

$$C_P = \frac{n!}{\prod k^{P_k} P_k!}$$

Now to add to Wouter's answer: see Section 2.11 of Herstein's book Topics in Algebra (2nd edition). For a group $G$, if $a,b, \in G$, then $b$ is said to be a conjugate of $a$ if there exists an element $c\in G$ such that $b = c^{-1}ac$. It is easy to show that this defines an equivalence relation on $G$, so let's define $C(a)$ to be the the equivalence class of $a$ (the set of elements conjugate to $a$). From p88. two permutations in $S_n$ are conjugate if and only if they have the same type. So there are $|P(n)|$ different conjugate classes, and their sizes are determined by $|C(a)| = C_{\text{type}(a)}$. This leads to clear intuition on your identity

$$\sum_{P} \prod \frac{1}{k^{P_k} P_k!} = \sum_{P} \frac{C_P}{n!} = 1$$

Adding another combinatorial interpretation, define the normalizer of a in G as the set of elements that commute with $a$: $N(A) = \{x \in G \; | \; xa = ax\}$. I believe the modern lingo is centralizer rather than normalizer, but we'll stay true to Herstein (2nd ed.). We have the following counting principle, which is Theorem 2.11.1. If $G$ is a finite group, then the number of elements conjugate to $a$ is the index of the normalizer of $a$ in $G$. That is,

$$|C(a)| = \frac{ |G|}{|N(a)|}$$

Thus, we find that if $a$ has type $(P_1,...,P_n)$, then the number of permutations that commute with $a$ is $|N(a)| = \prod k^{P_k} P_k!$.

• small typo in your multinomial expression: there should be no factorial in the denominator. – Wouter M. Jan 18 '15 at 10:19
• very nice answer, thank you – David Holden Jan 18 '15 at 13:06
• @WouterM. I believe the multinomial is correct. The factorials get multiplied out by the $\prod (k-1)!^{P_k}$ that accounts for the permutations of each cycle. – Andrew Szymczak Jan 18 '15 at 15:57
• @Drew: you're right, my bad. – Wouter M. Jan 18 '15 at 17:13