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

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.

• The phrase "successive bins" implies the bins are in some sort of order - is this linear or cyclic? – Martin Rattigan Mar 22 '17 at 1:22
• I dont know what is meant by cyclic vs linear but the bins are placed in a line 1..n. You then place the balls in the bins. Two successive bins can have a ball each but there should be no two successive empty bins. Also at most one ball per bin. – user3079275 Mar 22 '17 at 1:26
• OK. That's what I meant by linear. It makes a difference if they are placed in a circle. – Martin Rattigan Mar 22 '17 at 1:30

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.