In how many ways can we distribute $k$ identical balls into $n$ different boxes

balls-in-binscombinationscombinatoricspermutations

In how many ways can we distribute $k$ identical balls into $n$ different boxes
so that each box contains atmost one ball and no two consecutive boxes
are empty.

My Approach:

First I filled the $k$ boxes out of $n$ box with $k$ identical balls. Then I arranged remaining $(n-k)$ boxes between $(k+1)$ gaps formed by $k$ boxes and this can be done in ${k+1 \choose n-k}$. and this match with the given answer.

My Doubt: According to me I must select $k$ boxes out of $n$ boxes to put $k$ identical balls. So according to me answer must be ${n\choose k}{k+1\choose n-k}$.

What I am thinking wrong in second Approach?

Is there any other way to solve this problem?

Best Answer

Your first approach is indeed correct. Here is an alternate (much more laboriously exhaustive) way of thinking about the problem:

Part I

You can reformulate the problem, by instead thinking about arranging two types of "tiles": (A) a box containing a ball, and (B) a box lacking a ball, followed by a box containing a ball.

For example, suppose $n=9$ and $k=6$. In this case, you must have $n-k=3$ empty boxes. Thus, you will have $n-k=3$ of "tile B". This leaves $n-2(n-k)=2k-n=3$ balls to be used as instances of "tile A".

To illustrate the idea: let $(1)$ denote "tile A", i.e. a box containing a ball, and let $(01)$ denote "tile B", i.e. a box lacking a ball followed by a box containing a ball. Here are a few arbitrary arrangements of these "tiles":

$$ (1)(1)(01)(1)(01)(01) = 1,1,0,1,1,0,1,0,1 \\ (01)(01)(1)(1)(1)(01) = 0,1,0,1,1,1,1,0,1 \\ (01)(1)(1)(01)(01)(1) = 0,1,1,1,0,1,0,1,1 $$

As you may observe from these examples, we have $(n-k)+(2k-n)=k$ total "tiles", out of which we must choose $n-k$ positions for the $(01)$s. The total number of ways we can do this is $\binom{k}{n-k}$.

Part II

At this point, we run into a problem: our two tiles $(1)$ and $(01)$ admit every way to produce a sequence with ends with a filled box, i.e. $1$... but no way to produce a sequence which ends with an empty box, i.e. $0$. For example, the following are valid ball arrangements with no two consecutive empty boxes, but there is no way to divide them up into $(1)$ and $(01)$ only:

$$ 0,1,0,1,1,1,1,1,0 = (01)(01)(1)(1)(1)(1)0 \\ 1,0,1,1,1,1,0,1,0 = (1)(01)(1)(1)(1)(01)0 \\ 1,1,1,1,0,1,0,1,0 = (1)(1)(1)(1)(01)(01)0 $$

Thus, we must introduce a new tile: let $(0)$ denote "tile C". However, "tile C" comes with a couple of very specific restrictions: (i) it can only appear at most once in any tile set, and (ii) if it does appear, it must be the very last tile. These restrictions make it so that we can effectively ignore "tile C" when enumerating the sequences of boxes which end with an empty box.

For example: in the three sequences shown above which end in $0$, we can effectively just ignore the $0$ as it does not affect anything, and observe that from $k$ "tiles", we must choose $n-k-1$ positions for the $(01)$s.

Part III

In Part I, we showed that the number of combinations which end in $1$ is $\binom{k}{n-k}$. Subsequently, in Part II, we showed that the number of combinations which end in $0$ is $\binom{k}{n-k-1}$. "Combinations which end in $1$" and "combinations which end in $0$" are two mutually exclusive, collectively exhaustive sets, which together comprise the set of all possible combinations. Thus, the total number of possible combinations is simply the sum of the two results from Parts I & II:

$$ \binom{k}{n-k} + \binom{k}{n-k-1} \\ = \binom{k+1}{n-k} $$

Note that this solution is valid only when $n/2 \le k \le n$; if not, then the answer is $0$. If $k < n/2$, then there are less than half as many balls as boxes, which makes it impossible to avoid two consecutive empty boxes occurring somewhere. And if $k > n$, then there are more balls than boxes, which by the pigeonhole principle implies that at least one box must have two or more balls.

Brute force check with Python 3.x

The following Python script does the following: for $1\le n \le 20$, and for $\lceil{n/2}\rceil \le k \le n$, (i) manually lists out all the distinct valid combinations, and counts them; and (ii) calculates the number of distinct valid combinations, by way of $\binom{k+1}{n-k}$. The output confirms that for each checked $(n,k)$, the values from (i) and (ii) agree.

from math import ceil, comb

def distinct_permutations(iterable):
    iterable = sorted(iterable)
    size = len(iterable)
    while True:
        yield tuple(iterable)
        for i in range(size - 2, -1, -1):
            if iterable[i] < iterable[i + 1]:
                break
        else:
            return
        for j in range(size - 1, i, -1):
            if iterable[i] < iterable[j]:
                break
        iterable[i], iterable[j] = iterable[j], iterable[i]
        iterable[i + 1 :] = iterable[: i - size : -1]

def test(n_max):
    agree = []
    for n in range(1,n_max+1):
        k = ceil(n/2)
        while k <= n:
            boxes = '1'*k + '0'*(n-k)
            all_combos = [''.join(c) for c in distinct_permutations(boxes)]
            valid_combos = [c for c in all_combos if '00' not in c]
            manual = len(valid_combos)
            calc = comb(k + 1, n - k)
            agree.append(manual==calc)
            k += 1
    return all(agree)

if __name__ == '__main__':
    print(test(n_max=20))

Output:

True
Related Question