# identity proof for partitions of natural numbers

## Definition:

A tuple $\lambda = (\lambda_1, \cdots, \lambda_k)$ of Natural Numbers is called a numeric partition of n if $1 \leq \lambda_1 \leq \cdots \leq \lambda_k$ and $\lambda_1 + \cdots + \lambda_k = n$ and is written as $\lambda \vdash n$. A numeric partition $\lambda = (\lambda_1, \cdots, \lambda_k) \vdash n$ can be as well written as $\lambda = [m_1, \cdots, m_n]$ with $m_i = \# \{j | \lambda_j = i\}$ and $\sum_{k=1}^{n} m_k*k = n$.

## Exercise:

$g_k(\lambda) := \# \{i | m_i(\lambda) \geq k\}$.

Example:

$\lambda = [5,3,3,3,2,2,0,\cdots,0] \Rightarrow m_3(\lambda) = 3, g_2(\lambda) = 6$

Prove for fix $n,k \geq 1$ $$\sum\limits_{\lambda \vdash n} m_k(\lambda) = \sum\limits_{\lambda \vdash n} g_k(\lambda)$$

First I tried to write down all numeric partitions of $n = 3$

$$\{\lambda | \lambda \vdash 3 \} = \{(1,1,1),(1,2),(3)\}$$

$$\begin{array}{l|cccccc} \lambda & m_1 & m_2 & m_3 & g_1 & g_2 & g_3 \\\hline (1,1,1) & 3 & 0 & 0 & 1 & 1 & 1 \\ (1,2) & 1 & 1 & 0 & 2 & 0 & 0 \\ (3) & 0 & 0 & 1 & 1 & 0 & 0 \\\hline \sum & 4 & 1 & 1 & 4 & 1 & 1 \end{array}$$

Suppose we could show that the number of partitions with $m_l \geq k$ is equal to the number of partitions with $m_k \geq l$. It then follows that $$\sum_{p \vdash n} m_k(p) = \sum_{l \geq 1} \sum_{p \vdash n}[m_k(p) \geq l] = \sum_{l \geq 1} \sum_{p \vdash n}[m_l(p) \geq k] = \sum_{p \vdash n} g_k(p).$$ In order to prove the claim, it is enough to restrict ourselves to partitions whose only parts are $k,l$. Indeed, an arbitrary partition of $n$ decomposes uniquely as a partition of $n_1+n_2$, where $n_1$ is a partition using $k,l$, and $n_2$ is a partition not using $k,l$. Furthermore, we can assume that $k,l$ are relatively prime (otherwise, cancel the GCD).

We show that the number of $k,l$-partitions with $m_l < k$ is equal to the number of $k,l$-partitions with $m_k < l$. Notice that since $k,l$ are relatively prime, there's at most one $k,l$-partition with $m_l < k$ and at most one $k,l$-partition with $m_k < l$. We show that if there is a $k,l$-partition with $m_l < k$ then there is one with $m_k < l$.

Suppose there's a $k,l$-partition with $m_k < l$. If for that partition also $m_l < k$, we're done. Otherwise, repeatedly replace $k$ parts of size $l$ with $l$ parts of size $k$ until you reach a partition with $m_l < k$.

Here is an alternative proof for the claim about $k,l$-partitions, for coprime $k,l$.

Let $$\alpha = (k^{-1}n) \bmod{l}, \quad \beta = (l^{-1}n) \bmod{k}.$$ Here $k^{-1}$ is taken with respect to $l$, and vice versa.

Define the following operation ("conjugation") on pairs $(a,b)$ that solve $ak+bl=n$: $$(a,b)' = \left(\frac{l}{k}(b - \beta) + \alpha, \frac{k}{l}(a - \alpha) + \beta\right).$$ One can check the following properties:

1. Conjugation takes a solution of $ak+bl=n$ to another solution.
2. Conjugation is an involution (it is its own inverse).
3. If there's an integral solution $(a,b)$ with $0 \leq a < l$ then its conjugate $(a',b')$ has $0 \leq b < k$, and vice versa.
4. If $kl|n$ then $(a,b)' = (b,a)$.

Here are some examples, with $k = 5$ and $l = 3$. One can check that $k^{-1} \bmod{l} = 2$ and $l^{-1} \bmod{k} = 2$.

If $n = 30$ then $(a,b)'=(b,a)$. We have $(0,10)' = (6,0)$ and $(3,5)' = (3,5)$.

If $n = 40$ then $\alpha = 80 \bmod{3} = 2$ and $\beta = 80 \bmod{2} = 0$. Thus $(a,b)' = (3/5b + 2, 5/3(a - 2))$. We have $(8,0)' = (2,10)$ and $(5,5)' = (5,5)$.

If $n = 7$ then $\alpha = 14 \bmod{3} = 2$ and $\beta = 14 \bmod{2} = 0$. This time there are no minimal solutions. Instead, we have the pair $(2,-1)' = (7/5,0)$.

Here's a proof using generating series. The advantage of this proof is that it requires no thought.

The usual generating series for partitions is $$P = \frac{1}{(1-x)(1-x^2)(1-x^3)\cdots}.$$ The coefficient of $x^n$ is the number of partitions of $n$.

Suppose we want to sum over $m_k$. So we need to replace the factor $1/(1-x^k)$ with $$x^k + 2x^{2k} + 3x^{3k} + \cdots = \frac{x^k}{(1-x^k)^2}.$$ So the generating series for $\sum m_k$ is $$M = \frac{x^k}{1-x^k} P.$$

Now let's sum over $g_k$. How much do $1$-parts contribute to the sum? We only count them if there are at least $k$ of them. So we need to replace $1/(1-x)$ with $$x^k + x^{k+1} + \cdots = \frac{x^k}{1-x}.$$ So $1$-parts contribute $x^k P$. Similarly, $2$-parts contribute $x^{2k} P$, and so on. In total, the generating series for $\sum g_k$ is $$G = (x^k + x^{2k} + x^{3k} + \cdots) P = \frac{x^k}{1-x^k} P = M.$$

• Thank you for your answer! There's only one thing I don't understand: What were the steps to get to your definition of P? – muffel May 22 '11 at 6:41
• @muffel: This is very standard, you can look at any book discussing partitions, e.g. Hardy and Wright's. – Yuval Filmus May 22 '11 at 17:07
• I found a definition, thank you! The only thing left I don't understand is the second step where you sum over $g_k$. For k = 1 we (just) need to count the amount of different values, how do you package that to $x^k + x^{2k}+\cdots$? Why do p-parts contribute $x^{2k}$? – muffel May 22 '11 at 19:09
• @muffel: We separately count the contribution for $p$-parts for each $p$. That contribution turns out to be $x^{pk}P$. In total we get $x^k/(1-x^k)\cdot P$. Contrast it with the combinatorial proof. – Yuval Filmus May 22 '11 at 20:45
• @muffel: The combinatorial proof is more interesting than I had originally thought! Check it out. – Yuval Filmus May 23 '11 at 15:55