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