5
$\begingroup$

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} $

1 Answers 1

6

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

  • 1
    @muffel: The combinatorial proof is more interesting than I had originally thought! Check it out.2011-05-23