1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Keith McClary Feb 11 at 4:32
  • $\begingroup$ 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$. $\endgroup$ – Izaak Coleman Feb 11 at 4:55
  • $\begingroup$ 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. $\endgroup$ – Keith McClary Feb 11 at 16:34
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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