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?

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

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.

  • $\begingroup$ thanks very much for that link. $\endgroup$ – 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! $.

  • $\begingroup$ small typo in your multinomial expression: there should be no factorial in the denominator. $\endgroup$ – Wouter M. Jan 18 '15 at 10:19
  • $\begingroup$ very nice answer, thank you $\endgroup$ – David Holden Jan 18 '15 at 13:06
  • $\begingroup$ @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. $\endgroup$ – Andrew Szymczak Jan 18 '15 at 15:57
  • $\begingroup$ @Drew: you're right, my bad. $\endgroup$ – Wouter M. Jan 18 '15 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.