# 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.

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?

• In your example, consider 10101. How many ways are there to add two more 0s in four places (either at the ends or between the 1s ? – Keith McClary Feb 11 '19 at 4:32
• Sorry, I miss understood. I suppose you could have two possible slots aside each character in 10101 for the two remaining zeros. This would retain the requirement. So __1__0__1__0__1__ which gives 12 possible slots, choose 2 so $_{12}C_2 = 66$. – Izaak Coleman Feb 11 '19 at 4:55
• No, I was suggesting that you have three occupied slots and you should consider how many ways the unoccupied slots can be distributed around them, but I see that is the hard way to do it. – Keith McClary Feb 11 '19 at 16:34

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.