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.

Possible Duplicate:
Combinatorial proof
Arranging people in a row

This is a home work problem that I am not able to proceed. Please advice.

share|improve this question

marked as duplicate by Marc van Leeuwen, draks ..., tomasz, rschwieb, sdcvvc Oct 12 '12 at 21:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Please take the occasion to reformulate your question less succinctly in the body of the text, using complete sentences. –  Marc van Leeuwen Oct 11 '12 at 8:47

2 Answers 2

Hint: Select $k$ from $n-k+1$ balls. Can you place the remaining $k-1$ unselected balls such as to establish a one-to-one correspondence between these arrangements and the desired arrangements?

share|improve this answer

Think of the $k$ chosen balls as dividers separating the $n-k$ unchosen balls into $k+1$ groups. For instance, choosing $3$ balls out of $8$ and representing the chosen balls by x and the others by o, I might have oxoooxox, dividing the unchosen balls into groups of $1,3,1$ and $0$ balls. Or I might have xooxooxo, with the chosen balls dividing the unchosen balls into groups of $0,2,2$, and $1$ ball. Other possibilities are xooxooox ($0,2,3,0$) and oxoxoxoo ($1,1,1,2$).

The first and last groups can be empty, but the others have to contain at least one ball in order to keep the chosen balls apart. Let $x_0,x_1,\dots,x_k$ be the numbers of unchosen balls in the $k+1$ slots, reading from left to right. Then $x_0+x_1+\ldots+x_k=n-k$, $x_0,x_k\ge 0$, and $x_1,\dots,x_{k-1}\ge 1$. You can simplify matters by letting $y_0=x_0,y_1=x_1-1, y_2=x_2-1,\dots,y_{k-1}=x_{k-1}$, and $y_k=x_k$, so that $y_i$ is the number of unchosen balls in slot $i$ beyond the minimum required. The minimum uses up $k-1$ balls, so the extras add up to $n-k-(k-1)=n-2k+1$:

$$y_0+y_1+\ldots+y_k=n-2k+1\;,$$

and the only constraint on the $y_i$’s is that they be non-negative integers. This is a standard stars-and-bars problem; the material at the link should enable you to finish the problem without too much trouble.

share|improve this answer

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