Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
    
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
    
@Yuval-Filmus Regarding your first proof: You say that using conjugation $m_l \geq k$ can be transformed into $m_k \geq l$. So take a look at the partition (3,1) of which the conjugated partition is (2,1,1). $m_3 \geq 1 \neq m_1 \geq 3$ or am I understanding something wrong? –  muffel May 23 '11 at 9:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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