how interpret this partition identity?

Question

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?

Answer 1

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.

Answer 2

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