# How many partitions of $n$ are there?

Considering a partition to be an ordered $n$-tuple $(m_1, m_2, m_3, ..., m_n)$ with all the numbers $m_i$ natural, $m_1 \le m_2 \le m_3 \le ... \le m_n$, and $m_1+m_2+...+m_n=n$: how many of those $n$-tuples are there?

Also, what is the link between partitions and Cauchy's observation that the number of permutations in $S_n$ that can be written as a product of $k_1$ lenght-1 cycles, $k_2$ lenght-2 cycles, ..., $k_n$ lenght-n cycles (all the cycles being disjoint) is: $$\frac{n!}{k_1!k_2!k_3!\cdots k_n!\cdot 1^{k_1}2^{k_2}3^{k_3} \cdots n^{k_n}}$$

• In the question, the only n-uple coresponding to 2+3 when n=5 is (0,0,0,2,3). Apr 7, 2016 at 9:10
• That is because if we give k_1 the value m_n - m_(n-1), and we give k_2 the value m_(n-1) - m_(n-2), and so on until we give k_(n-1) the value m_2 - m_1 and k_n = m_1, we get the sum of all the distinct elements in the cycles that is k_1 + 2*k_2 + 3*k_3 + ... + n*k_n to be exactly n. Apr 7, 2016 at 9:17

There is a famous generating function for this: I will provide the generating function, then talk a little bit about why it is correct.

The generating function is $$P(q) = \prod_{k=1}^\infty (1 - q^k)^{-1} = 1 + q +2q^2 + 3q^3 + 5q^4 + 7q^5 + 11q^6 + \cdots.$$

Why is it correct? Well, write each individual term in the product out: The first few are $$\frac{1}{1 - q} = 1 + q + q^2 + q^3 + q^4 + \cdots$$ and $$\frac{1}{1 - q^2} = 1 + q^2 + q^4 + q^6 + q^6 + \cdots$$ and $$\frac{1}{1 - q^3} = 1 + q^3 + q^6 + q^9 + q^{12} + \cdots$$ etc. So what is the coefficient of $q^n$ in the resulting series? It will be all ways of taking terms from some multipland whose total exponent adds up to $n$. If you take a term $q^{mk}$ from $(1 - q^k)^{-1}$ then this should be thought of as $k + \cdots + k$ ($m$ times). In particular, let's look at the coefficient of $q^3$. Then we get $$(1 + q + q^2 + \color{red}{q^3} + \cdots) \cdots$$ and $$(1 + \color{red}{q} + q^2 + \cdots)(1 + \color{red}{q^2} + q^4 + \cdots) \cdots$$ and $$(\color{red}{1} + q + q^2 + \cdots)(\color{red}{1} + q^2 + q^4 + \cdots)(1 + \color{red}{q^3} + q^6 + \cdots) \cdots$$ corresponding to the three partitions $1 + 1 + 1$, $1 + 2$, and $3$.

Note that your condition that the partition be ordered, but that $m_1 \leq m_2 \leq \cdots$ is equivalent to taking an unordered partition which is what I've described here, since we can always rearrange our terms in increasing order.

Note further that a lot of information about this can be found at http://oeis.org/A000041

As for the second part of the question: First note that the conjugacy class of any element $\sigma \in S_n$ yields a partition of $n$ by looking at its cycle decomposition. In particular, this yields a bijection between partitions of $n$ and conjugacy classes of $S_n$. Accordingly, for a fixed partition of $n$ we are looking at determining the size of such a conjugacy class. Now, the group $S_n$ acts on a conjugacy class $C$ via conjugation. The orbit-stabilizer theorem tells us that $$n! = |S_n| = |C(\sigma)| \cdot |Stab_{S_n}(\sigma)|$$ for any fixed $\sigma \in C(\sigma)$. So if we can determine the order of a stabilizer under the conjugation action, then we are done. If we write $$\sigma = \underbrace{\sigma_1^1 \cdots \sigma_{k_1}^1}_{k_1} \underbrace{\sigma_1^2 \cdots \sigma_{k_2}^2}_{k_2} \cdots$$ (where the exponents refer to the length of the cycle), then we note that a conjugation which fixes this must

1. Permute the $k_i$-cycles
2. only act as cyclic permutations on those cycles

In any case, there are $k_i!$ permutations of the $i$ cycles, and for each of those there are $i$ cyclic permutations. Thus for each $i$, we have $k! i^{k_i}$ permutations which fix all of those. Putting it together, the stabilizer of $\sigma$ has order $$\prod_{i=1}^n k_i! i^{k_i}$$ which yields what you're looking for; specifically, $$|C(\sigma)| = \frac{|S_n|}{|Stab_{S_n}(\sigma)|} = \frac{n!}{\prod_{i=1}^n k_i! i^{k_i}}$$

• Wow that is nicely explained, thank you. Do you happen to know about the second part of the question, about the permutations that can be factorised in type (k_1,k_2,...,k_n) distinct cycles? Apr 7, 2016 at 9:26
• Done! Hopefully that is clear enough. Apr 7, 2016 at 9:49
• Simply amazing. Thank you! Apr 7, 2016 at 9:51
• My approach was leaning towards counting and combinatorics. This is so elegant. Apr 7, 2016 at 9:52
• Generating functions and group actions for the win! Apr 7, 2016 at 9:53