Number of binary sequences with no consecutive ones.

Question

So I've got a problem that says
"How many ways are there go give $k$-identical biscuits to $n$-different children if each child gets at least one biscuit?"
I figured I'd do it using binary sequence. My approach is using $1$'s as children (separators) and $0$'s as biscuits. Since every child must get at least one biscuit then the sequence can't start with one (there would be no $0$'s "biscuits" to the left) and there can't be $1$'s next to each other (some $1$ "child" would get no biscuit). Now I already know the answer to that problem and it is $\binom{k-1}{n-1}$ and my problem is understanding why it is $k-1$ and not $k$. Clearly $n-1$ is because we only need $n-1$ separators to have $n$ divisions but why is it not $k$ instead of $k-1$? I think we have $k$ places for $1$'s to place and not $k-1$.

Answer 1

First we give each child a biscuit so that $k-n$ biscuits are over.

Then with stars and bars we find $$\binom{k-n+(n-1)}{n-1}=\binom{k-1}{n-1}$$possibilities.

Answer 2

HINT:

You should start by giving every child a biscuit first so that condition is solved. Further think about how many biscuits are left and in how many ways can you distribute these among the $n$ children.

Hope this helps :)

For these type of problems generating functions can also be a good approach. But in this case I would consider it an overshoot.

Answer 3

For the binary sequence approach:

You have a $0$ at the beginning of your sequence. Because a "$1$" is always followed by a "$0$", you can build the remainder of the sequence by putting $n-1$ substrings "$10$" and $k-n$ substrings "$0$". So you have $n-1$ elements of one type and $k-n$ of other type, so you get $$ \binom{(n-1)+(k-n)}{n-1} = \binom{k-1}{n-1} $$ as the number of ways.

Answer 4

An assignment of $k$ biscuits to $n$ children with each child receiving at least one biscuit can be represented by stars and bars. For example if $k=5$, and $n=4$ and the distribution is $(1,2,1,1)$, we can represent it by $$ \star\mid\star\,\star\mid \star\mid\star $$ Choosing $n-1$ bars out of $k-1$ "gaps" between stars uniquely defines a distribution. Hence there are $$ \binom{k-1}{n-1} $$ distributions. Alternatively you can use the method of generating functions. Indeed, note that $$ F(x)=\frac{x^n}{(1-x)^n}=(x+x^2+\dotsb)^n=\sum_{k=0}^\infty\left( \sum_{\alpha_1+\dotsb\alpha_n=k;\, \alpha_i\geq1} x^{\alpha_1+\dotsb\alpha_n}\right). $$ Hence its suffices to find the coefficient of $x^k$ in $F(x)$. But $$ [x^k]F(x)=[x^{k-n}](1-x)^{-n}=\binom{n+(k-n)-1}{n-1}=\binom{k-1}{n-1} $$ where we have used the binomial theorem $$ (1-x)^{-n}=\sum_{k=0}^{\infty}\binom{-n}{k}(-1)^kx^k =\sum_{k=0}^{\infty}\binom{n+k-1}{n-1}x^k. $$