Distributing $k$ balls into $n$ bins with two conditions

Question

I have $n$ bins and $k$ balls such that $n \lt 2k$.

In how many ways can I distribute the $k$ balls in the $n$ bins subject to following constraints:

• 1) A bin gets max one ball.

• 2) No two successive bins are empty.

Not sure if there is a clean solution to this. Have been thinking about it for a bit.

Answer 1

Let $1$ stands for an empty bin and $0$ stands for a full bin. You want to count how many strings like $0100100101$ are there, with length $n$, exactly $k$ zeroes in them and no consecutive $1$s. You may build such strings by first placing $k$ consecutive zeroes, then choosing $n-k$ places (among the $k+1$ spaces between consecutive zeroes, at the beginning or at the end) where to put a $1$.

The answer is so given by $\large\binom{k+1}{n-k}$ due to stars and bars.