The number of way to distribute n indistinguishable balls into k indistinguishable boxes arbitrarily

Question

Before even attempting at the proof, I need a clarification of a point in the question. I don't understand how the $k$ in $k \geq \lambda_1\geq ...\geq \lambda_r\geq 1$ is relevant. For $n=7$ and $k=3$, for example, isn't $\{1,5,1\}$ a valid multiset of ball distribution, but $(5,1,1)$ is not a valid integer partition of 7, since $\lambda_1 = 5 > 3 = k$?

Also, to prove the statement, I'm thinking of setting up a bijection between the set of ball distributions and the set of integer partitions of n. Would this be a sensible approach?

Answer 1

$n=\lambda_1+\lambda_2+ \ldots+\lambda_r$ corresponds to a partition of $n$ into $r$ parts. The condition $k \ge \lambda_i$ indicates that each part has size at most $k$.

Note that the question refers to number of partitions of $n$ into parts of size at most $k$. So $\{5,1,1\}$ is not the partition we're looking for with $n=7,k=3$ since there is one part (i.e. $5$) that has size greater than $3$. For example, with $n=7,k=3$, $\{3,2,1,1\}$ is a valid partition.

The condition $\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_r$ means that we don't have to care about the order of the parts when counting number of partitions. For example, $\{3,2,1,1\},\{3,1,1,2\}$ and $\{3,1,2,1\}$ are considered to be one partition $\{3,2,1,1\}$ for $n=7,k=3$. Why do we need this condition? Try to look back the situation with indistinguishable boxes. Do we have to care about the order of the boxes?

Also, to prove the statement, I'm thinking of setting up a bijection between the set of ball distributions and the set of integer partitions of n. Would this be a sensible approach?

Yes, bijection is the way to go. Before finding the main bijection, you should "translate" these two situations into one language. In particular, since the balls and boxes are indistinguishable, the number of distributions of $n$ indistinguishable balls into $k$ indistinguishable boxes is the same as number of partitions of $n$ into $k$ parts.

Answer 2

I don't understand how the $k$ in $k \geq \lambda_1\geq ...\geq \lambda_r\geq 1$ is relevant. For $n=7$ and $k=3$, for example, isn't $\{1,5,1\}$ a valid multiset of ball distribution, but $(5,1,1)$ is not a valid integer partition of 7, since $\lambda_1 = 5 > 3 = k$?

It seems that you are misunderstanding something.

For $n=7,k=3$, the number of the former is $8$ since we have $\{7,0,0\},$$\{6,1,0\},$$\{5,2,0\},$$\{5,1,1\},$$\{4,3,0\},$$\{4,2,1\},$$\{3,3,1\},$$\{3,2,2\}$. The number of the latter is $8$ since we have $(3,3,1),$$(3,2,2),$$(3,2,1,1),$$(3,1,1,1,1),$$(2,2,2,1),$$(2,2,1,1,1),$$(2,1,1,1,1,1),$$(1,1,1,1,1,1,1)$. So, the number of the former is equal to the number of the latter as claimed.

---

To see why they have the same number, let us take again the case where $n=7,k=3$.


$\quad\qquad$


The above shows :

• $\{7,0,0\}$ in the former corresponds to $(1,1,1,1,1,1,1)$ in the latter.
• $\{6,1,0\}$ in the former corresponds to $(2,1,1,1,1,1)$ in the latter.
• $\{5,2,0\}$ in the former corresponds to $(2,2,1,1,1)$ in the latter.
• $\{5,1,1\}$ in the former corresponds to $(3,1,1,1,1)$ in the latter.
• $\{4,3,0\}$ in the former corresponds to $(2,2,2,1)$ in the latter.
• $\{4,2,1\}$ in the former corresponds to $(3,2,1,1)$ in the latter.
• $\{3,3,1\}$ in the former corresponds to $(3,2,2)$ in the latter.
• $\{3,2,2\}$ in the former corresponds to $(3,3,1)$ in the latter.

In the former, we count the number of balls "vertically". In the latter, we count the number of balls "horizontally".

This explains why they have the same number.

Answer 3

You will need to find a bijection to send a multiset $\{a_1,a_2,\dots, a_k\}$ where $\sum a_i = n$ to a partition $(\lambda_1,\dots,\lambda_r)$ where $\sum \lambda_r = n$ and $3\ge\lambda_1\ge\dots\ge\lambda_r\ge 1$.

In your example, $\{1,5,1\}$ is a valid multiset and (5,1,1) is a partition, but (5,1,1) is not the partition that your bijection is supposed to send to. The problem does not say that the bijection is to send each multiset to the same partition using the elements in the multiset. You need to find a bijection so that it works.

Here's a hint: Using your example, {1,5,1} = {5,1,1} is a multiset, we will map it to (3,1,1,1,1), which is a partition of n=7 into parts of size at most k=3.

     1 *
     5 * * * * *
     1 *
       3 1 1 1 1