There are $n$ sticks lined up in a row and $k$ of them are to be chosen.
a) How many choices are there?
- There are $n \choose k$ choices or $nCk$
b) How many choices are there if no two of the chosen sticks can be consecutively?
- I think it's something like ${n-k+1} \choose k$ but I also think that whether there is an odd or even number of sticks matters… but I don't know how to show that.
c) How many choices are there if there must be at least $\ell$ sticks between each pair of chosen sticks?
Best Answer
Hint: Count the spaces between chosen sticks. Define $x_1$ to be the number of sticks before the first selected one, $x_2$ to be the number of sticks between the first and second selected ones, etc, and $x_{k+1}$ to be the number of sticks after the last selected stick.
Then $x_1 + x_2 + \dots + x_{k+1} = n - k$. Your constraints turn into constraints on the variables, i.e. for a) $x_i \geq 0$ for all i, for b) $x_1,x_{k+1} \geq 0$ and $x_2,\dots,x_k \geq 1$, etc.
Can you solve it now? (The $\binom{n+k-1}{k}$ should be useful...)