2
$\begingroup$

As the title says I need to find the number of ways to to place 3 red, 4 blue and 5 green wagons such that no 2 blue wagons were standing next to each other. The wagons of the same color are considered completely identical.

I think I solved it, but would like to have somebody to check it and tell if it's correct.

So my approach is to first count all possible combinations of these 12 wagons and then subscribe the combinations in which there are at least 2 blue wagons next to each other. The total number of combinations is:

$C_{12}^{3} * C_{9}^{4} * C_{5}^{5} = 27720$

The number of combinations in which at least 2 blue wagons are standing next to each other (that's the part I have the most doubts about): There are 11 ways to place 2 blue wagons next to each other if we have 12 places for wagons (1 and 2, 2 and 3, etc.). Once we've placed them this way, it doesn't matter where we place another 2 blue wagons. So we have $C_{10}^{2} $ ways to do it. And the number of combinations with blue wagons next to each other is 11 * 45 = 495

And the final answer would be 27720 - 495 = 27225.

$\endgroup$

1 Answer 1

5
$\begingroup$

Here is a different approach.

We first line up the three red and five green wagons (leaving enough space between each pair of wagons so that another wagon can be parked between them). This can be done by choosing which three of the eight positions will be reserved for the red wagons, which can be done in $\binom{8}{3}$ ways. We now choose four of the nine available spaces (seven between successive pairs of the eight wagons that have already been parked and two at the end) in which to place the blue wagons, which can be done in $\binom{9}{4}$ ways. Therefore, the number of ways that we can arrange three red, four blue, and five green wagons so that no two blue wagons are consecutive is $$\binom{8}{3} \cdot \binom{9}{4} = 7056$$

To make your approach work, we have to use the Inclusion-Exclusion Principle, with the cases being at least two consecutive blue wagons, at least three consecutive blue wagons, and all four blue wagons being consecutive. The case of two consecutive blue wagons is tricky since counting the cases in which there are at least two consecutive blue wagons count cases in which there are two disjoint pairs of blue wagons twice.

As you realized, the number of arrangements of three red, four blue, and five red wagons is $$\binom{12}{3}\binom{9}{4}\binom{5}{5} = \frac{12!}{3!4!5!}$$ We must subtract from these the number of arrangements in which at least two blue wagons are consecutive.

The number of ways in which at least two blue wagons are consecutive can be found by thinking of the twelve wagons as a pair of blue wagons, two additional blue wagons, three red wagons, and five green wagons. This gives us a total of eleven objects. We can place the pair of blue wagons in $\binom{11}{1}$ ways, the other two blue wagons in $\binom{10}{2}$ ways since ten places remain after the pair is placed, the three red wagons in the eight remaining spaces in $\binom{8}{3}$ ways, and the five green wagons in $\binom{5}{5}$ ways. This yields $$\binom{11}{1}\binom{10}{2}\binom{8}{3}\binom{5}{5} = \frac{11!}{1!2!3!5!}$$ arrangements in which two blue wagons are consecutive. However, we have counted each case in which there are two disjoint pairs of blue wagons twice. Since a pair can begin in any of the first eleven places, there are $\binom{11}{2}$ places to start a pair. However, $\binom{10}{1}$ of these are consecutive, so the pair would not be disjoint. Thus, there are $\binom{11}{2} - \binom{10}{1} = \binom{10}{2}$ (by Pascal's Identity) ways to place two disjoint pairs of blue wagons. Once they have been placed, there are eight spaces remaining. We can place the three red wagons in these eight spaces in $\binom{8}{3}$ ways and the five green wagons in the five remaining spaces in $\binom{5}{5}$ ways. Thus, there are $$\binom{10}{2}\binom{8}{3}\binom{5}{5} = \frac{10!}{2!3!5!}$$ arrangements in which there are two disjoint pairs of blue wagons. Thus, the number of arrangements in which at least two blue wagons are consecutive is $$\frac{11!}{1!2!3!5!} - \frac{10!}{2!3!5!}$$

The number of ways in which at least three blue wagons are consecutive can be found by thinking of the twelve wagons as ten objects, namely the three consecutive blue wagons, the other blue wagon, the three red wagons, and the five green wagons. We can place the trio of consecutive blue wagons in $\binom{10}{1}$ ways, the other blue wagon in one of the nine remaining spaces in $\binom{9}{1}$ ways, the three red wagons in the eight remaining spaces in $\binom{8}{3}$ ways, and the five green wagons in the last five spaces in $\binom{5}{5}$ ways. Hence, there are $$\binom{10}{1}\binom{9}{1}\binom{8}{3}\binom{5}{5} = \frac{10!}{1!1!3!5!}$$ ways of arranging the wagons so at least three blue wagons are consecutive.

The number of ways we can arrange the wagons in which all four blue wagons are consecutive can be found by thinking of the four blue wagons as one object. Then we have nine objects to place, the block of four consecutive blue wagons, the three red wagons, and the five green wagons. We can place the four consecutive blue wagons in $\binom{9}{1}$ ways, the three red wagons in $\binom{8}{3}$ ways, and the five green wagons in $\binom{5}{5}$ ways. Thus, there are $$\binom{9}{1}\binom{8}{3}\binom{5}{5} = \frac{9!}{1!3!5!}$$ arrangements in which all four blue wagons are consecutive.

By the Inclusion-Exclusion Principle, the number of arrangements of three red wagons, four blue wagons, and five green wagons in which no two blue wagons are consecutive is $$\frac{12!}{3!4!5!} - \left[\frac{11!}{1!2!3!5!} - \frac{10!}{2!3!5!}\right] + \frac{10!}{1!1!3!5!} - \frac{9!}{1!3!5!} = 7056$$ which agrees with the result obtained above.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .