1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The phrase "successive bins" implies the bins are in some sort of order - is this linear or cyclic? $\endgroup$ – Martin Rattigan Mar 22 '17 at 1:22
  • $\begingroup$ 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. $\endgroup$ – user3079275 Mar 22 '17 at 1:26
  • $\begingroup$ OK. That's what I meant by linear. It makes a difference if they are placed in a circle. $\endgroup$ – Martin Rattigan Mar 22 '17 at 1:30
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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