Given $N$ slots and $S$ objects to fill those slots, how many ways are there to fill the slots such that no two objects are adjacent.

Question

Given $N$ slots and $S$ objects to fill those slots, how many ways are there to fill the slots such that no two objects are adjacent?

I can't see a general pattern for this. If I take $N=7$ and $S = 3$, and let represent a slot as filled or empty as $1$ or $0$, respectively, I can represent the problem as a bitstring.

In the case above, when placing the first bit at the end: There are $2$ slots to place the first bit, pick one such that $1000000$. Now there are $5$ remaining slots to place the second bit, pick one such that $1010000$ and there are three remaining slots for the final bit. Hence we have $7 \cdot 5 \cdot 3$ ways.

However, when placing the first bit in the middle: There are $5$ possible ways to place the first bit, pick one such that $0100000$. There are now $4$ ways to place the second bit, pick one $0100100$. There is now one place for the final bit ($0100101$) such that there are $5 \cdot 4$ ways in this instance when placing the first bit at the aforementioned location (there are other outcomes further).

Is there a general pattern?

Answer 1

Method 1: Let's work with your bit string idea. Notice that each $1$ except the last must be immediately be followed by a $0$. For your example of three objects in seven slots, we would then have to count arrangements of $10, 10, 1, 0, 0$ in which the solitary $1$ must follow both $10$s. Doing so would force us to do casework. We can avoid that by appending an extra $0$ to the string, so we have to arrange $10, 10, 10, 0, 0$. Notice that no matter how we arrange the five objects, the final digit will be a $0$. Thus, the number of strings of length $8$ ending with $0$ in which no two of the three $1$s are consecutive is equal to the number of bit strings of length $7$ in which no two of the three $1$s are consecutive since there is only one way to fill the final slot. Treating each $10$ as a single object gives us five positions to fill. Choosing which three of them will be filled with $10$s completely determines the string. For instance, if we fill the first three slots with $10$s, we obtain $$10101000$$ which is equivalent to the string $1010100$, while if we fill the second, fourth, and fifth slots with $10$s, we obtain $$01001010$$ which is equivalent to the string $0100101$. The number of such strings is $\binom{5}{3}$ since we must select which three of the five positions will be filled with $10$s.

More generally, if we have $k$ objects to place in $n$ slots, we add an extra $0$ so that we can form a bit string of length $n + 1$ consisting of $k$ $10$s and $n + 1 - 2k$ $0$s. Then no two of the $1$s will be consecutive. The number of such bit strings is $$\binom{n + 1 - 2k + k}{k} = \binom{n - k + 1}{k}$$ since we must choose which $k$ of the $n - k + 1$ positions required for $k$ $10$s and $n + 1 - 2k$ $0$s will be filled with $10$s.

Method 2: Let's consider your example of three $1$s and four $0$s again. Place the four $0$s in a row. This creates five spaces, three between successive $1$s and two at the ends of the row. $$\square 0 \square 0 \square 0 \square 0 \square$$ To separate the ones, we must choose three of these five spaces in which to place the ones. If we choose the first three spaces, we obtain $$1010100$$ If we instead choose the second, fourth, and fifth spaces, we obtain $$0100101$$ The number of such choices is $\binom{5}{3}$.

More generally, if we have $k$ objects to place in $n$ slots, we form a bit string with $k$ $1$s and $n - k$ $0$s. We place the $n - k$ $0$s in a row, which creates $n - k + 1$ spaces in which we can insert the $1$s, $n - k - 1$ spaces between successive zeros and two at the ends of the row. To separate the $1$s, we must choose $k$ of these $n - k + 1$ spaces in which to place a $1$, which yields $$\binom{n - k + 1}{k}$$ which agrees with the answer we obtained above.