Why is this problem solved using 'stars and bars' theorem?

Question

We have a set of $n^2$ integer and each number of them is in interval $[1, n]$.

Every number from $1$ to $n$ is frequent $n$ times.

For example, $n = 3$ and set is $\{1, 1, 1, 2, 2, 2, 3, 3, 3\}$.

We also have $n$ boxes

The question is how many ways we can choose $n$ numbers from the set and distribute them into the $n$ boxes with one number appearing in each box such that the number (from the set) in the $i$th box is $\geq$ the number in the $(i-1)$st box?

For example: ($n = 3$)

• correct situation: $1, 1, 3$
• not correct situation : $1, 2, 1$

The solution is $C(n+n-1, n)$, but I can't understand why. Why is that correct?

Answer 1

Since the numbers must be arranged in nondecreasing order and one number is placed in each of the $n$ boxes, a distribution of numbers selected from the multiset $\{n \cdot 1, n \cdot 2, n \cdot 3, \ldots, n \cdot n\}$ is completely determined by how many times each number appears. For instance, if $n = 5$ and $2$ appears twice and each number larger than $2$ appears once, the distribution must be $2, 2, 3, 4, 5$ since the numbers must be arranged in nondecreasing order.

Let $x_i$ be the number of times the integer $i$ is selected, where $1 \leq i \leq n$. Since a total of $n$ numbers are selected,
$$x_1 + x_2 + \cdots + x_n = n$$ which is an equation in the nonnegative integers.

A particular solution of the equation corresponds to the placement of $n - 1$ addition signs in a row of $n$ ones. For instance, if $n = 5$, $$+ 1 1 + 1 + 1 + 1$$ corresponds to the solution $x_1 = 0$, $x_2 = 2$, $x_3 = x_4 = x_5 = 1$ and the distribution $2, 2, 3, 4, 5$. The number of solutions is the number of ways we can select which $n - 1$ of the $2n - 1$ positions required for $n$ ones and $n - 1$ addition signs will be filled with addition signs, which is $$\binom{n + n - 1}{n - 1} = \binom{2n - 1}{n - 1}$$ or, equivalently, which $n$ of the $2n - 1$ positions required for $n$ ones and $n - 1$ addition signs will be filled with ones, which is $$\binom{n + n - 1}{n} = \binom{2n - 1}{n}$$

Answer 2

This is the number of sequences of $n$ integers $(a_i)$ with:

$$1\leq a_1\leq a_2\leq \cdots\leq a_n\leq n\tag1$$

The multi-set is irrelevant, any such $(a_i)$ can be made from the set. If there were more than $n$ boxes, it becomes harder, because some solutions to (1) would not be allowed.

Letting: $b_1=a_1-1,$ $b_2=a_2-a_1,$ $\dots,$ $b_n=a_{n}-a_{n-1},$ $b_{n+1}=n-a_n.$ Then the $b_i\geq0,$ and $$b_1+\cdots +b_{n+1} =n-1.\tag 2$$

Also, given any sequence of non-negative intefers $b_i$ satisfy $(2),$ we can get a sequence $a_i$ satisfying $(1)$ with: $$a_k=1+b_1+\cdots+b_k$$

So counting cases of (1) is the same as counting cases (2), and (2) is the problem stars and bars is meant for, and stars and bars gives:

$$\binom{(n-1)+(n+1)-1}{(n+1)-1}=\binom{2n-1}{n} $$

---

There is a more direct relationship between $(1)$ and the binomial.

If $(a_i)$ satisfies $(1)$ then let $c_i=a_i+i-1.$ Then $$1\leq c_1<c_2<\cdots<c_n\leq 2n-1.\tag3$$

This means $C=\{c_1,\dots,c_n\}$ is a subset of $A=\{1,\dots,2n-1\}$ of size $n.$ Also, given an subset $C$ of $A$ of size $n$ then we can sort $C$ to get $c_1,\dots,c_n$ Which satisfy (3).$

Answer 3

You know that each section in the result box of length n will contain at most 3 representations from 1, 2, 3 and at minimum 0. Where stars and bars comes in is, you can set up 5 spaces: 2 where dividers go and 3 where “stars” go. The stars represent the number of times you draw from each distinct group (where the groups are 1, 2, 3). So if you have a divider in the first slot and second slots, you sample 3 times from the 3s. Likewise, if you have a divider in the 1st and 3rd slot, you sample 0 from the 1s, 1 from the 2s, and 2 from the 3s. This is equal to C(2n-1, n-1).
This is the basic intuition. The other answers are more rigorous