Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.