# Inequalities and binomial coefficients

Does anybody know a proof of the following assertion?

The number of solutions to the inequalities $1 \leq x_{1} \leq x_{2} \leq \ldots \leq x_{i} \leq n$ is $\binom{n+i-1}{i}$.

I would appreciate any hint (or hints) you wish to provide me with...

-
I assume the $x_j$ are integers? – Jonathan Christensen Nov 8 '12 at 19:27
This is called "the number of combinations with repetitions". The formula can be proved using the stars and bars trick. – Dan Shved Nov 8 '12 at 19:28

The numbers $x_k$ seem to have a lot of room to ‘slide around’ in the interval from $1$ to $n$, so they may seem hard to get a handle on. If you replace them with the gaps between them and throw in the gaps between $1$ and $x_1$ and $x_i$ and $n$, you get $i+1$ non-negative integers that are tied down a little more tightly.

To do this, let $x_0=1$ and $x_{i+1}=n$. For $k=0,\dots,i$ let $y_k=x_{i+1}-x_i$. Then

$$y_0+y_1+\ldots+y_i=(x_1-x_0)+(x_2-x_1)+\ldots+(x_{i+1}-x_i)=x_{i+1}-x_0=n-1\;,$$ since all of the other terms cancel out. The condition that $$1=x_0\le x_1\le x_2\le\ldots\le x_i\le x_{i+1}=n\tag{1}$$ is then equivalent to the conditions that

$$y_0+y_1+\ldots+y_i=n-1$$ and $y_k\ge 0$ for $k=0,\dots,i$. Counting the number of solutions to $(1)$ in non-negative integers is a standard stars-and-bars problem; the linked article has a decent explation of the reasoning that leads to the answer

$$\binom{n+i-1}i\;.$$

-
Thanks a bunch, Brian! – absalon Feb 11 '13 at 0:08
@absalon: You’re welcome! – Brian M. Scott Feb 11 '13 at 0:09

Imagine $n+i-1$ ordered items, from which $i$ are colored black and $n-1$ white. Say the positions are $1\leqslant b_1\lt b_2\lt\cdots\lt b_i\leqslant n+i-1$. Call $x_i$ the number of white blocks to the left of block $b_i$, plus $1$. Then $1\leqslant x_1\leqslant x_2\leqslant\cdots\leqslant b_i\leqslant n$.

This defines a bijection between the set of $(b_k)$ configurations and the set of $(x_k)$ configurations, and the cardinal of the set of $(b_k)$ configurations is ${n+i-1\choose i}$.

-