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?

  • 4
    $\begingroup$ 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. $\endgroup$
    – angryavian
    Jun 21, 2021 at 17:08
  • $\begingroup$ 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? $\endgroup$ Jun 21, 2021 at 17:10
  • 1
    $\begingroup$ 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$. $\endgroup$
    – plop
    Jun 21, 2021 at 17:15
  • $\begingroup$ @plop Nice, you should write this as an answer. $\endgroup$
    – angryavian
    Jun 21, 2021 at 17:34
  • $\begingroup$ I have edited the question, sorry for weak description $\endgroup$ Jun 21, 2021 at 17:37

3 Answers 3


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


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .