1
$\begingroup$

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

  • 0
    This is called "the number of combinations with repetitions". The formula can be proved using the [stars and bars](http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29) trick.2012-11-08

2 Answers 2

3

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

  • 0
    @absalon: You’re welcome!2013-02-11
1

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