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

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?

• Could you clarify "each box should have a number $\ge$ the number exists in the previous one"? (Does "number" refer to one of the $n^2$ numbers, or the number of elements that a box contains?) Your "correct" and "incorrect" examples are not very clear, since there are 9 numbers in 3 boxes, but you only give three numbers. Jun 21, 2021 at 17:08
• If I understand the problem correctly, you want to select $n$ numbers from the $n^2$ available numbers, placing one number in each box so that the numbers appear in nondecreasing order. Is that correct? Jun 21, 2021 at 17:10
• You can model the problem by having variables $x_1,y_2,...,y_n,s$, where $x_1$ represents the number in the first box, $y_{i}$ represents the difference between the number in the $i$-th box and the $(i-1)$-th box, for $i=2,...,n$ and $s$ the difference between $n$ and the number in the last box. Then $x_1>0, y_2\geq0,...,y_n\geq0, s\geq0$. We should have $x_1+y_2+...+y_n+s=n$. Now you can change variable $y_i=x_i-1$ for $i=2,3,...,n$ and $s=x_{n+1}-1$. Now $x_1,x_2,...,x_{n+1}>0$ and $x_1+...+x_{n+1}=2n$.
– plop
Jun 21, 2021 at 17:15
• @plop Nice, you should write this as an answer. Jun 21, 2021 at 17:34
• I have edited the question, sorry for weak description Jun 21, 2021 at 17:37

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

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

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

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