2
$\begingroup$

Make sequence of $9$ balls from 3 red, 3 blue, 3 green, in such a way that no two balls of the same colour are next to each other. In how many different ways can you do this? (symmetric arrangements must be counted only once).

To start with, all possible arrangements are $9! = 362880$.

$\endgroup$
  • $\begingroup$ The number of distinguishable arrangements of $3$ red, $3$ blue, and $3$ green balls is $$\binom{9}{3}\binom{6}{3}\binom{3}{3} = \frac{9!}{3!3!3!}$$ You then have to exclude those cases in which a pair of balls of the same color are adjacent. $\endgroup$ – N. F. Taussig Dec 16 '17 at 20:30
  • $\begingroup$ @N.F.Taussig: right. For adjacent: For each colour, say red (R), once one R ball is placed, there are $$\binom{8}{2}$$ ways to get the other two red, and only 3 of these have 2 Rs next to each other. Or: all ways to have R arranged so to have at least 2 adjacent, we can have 7 positions for RRR and 8 positions for RR. For each of the 7 of RRR we then have $$\binom{6}{3}\binom{3}{3} = 20$$ ways for the rest of balls (so 7*20=140) and for each of the 8 of RR, we can have $$\binom{7}{3}\binom{4}{3}\binom{1}{1} = 140$$ ways for the rest, so in total 8*140. All in all 1260. Am I missing any? $\endgroup$ – Alex.vollenga Dec 17 '17 at 8:42
  • $\begingroup$ When you pose a question here, it is expected that you include your own thoughts on the problem. To avoid having your question down voted or closed, you should include your attempt and explain where you are stuck in the question itself. $\endgroup$ – N. F. Taussig Dec 17 '17 at 12:14
7
$\begingroup$

We have nine positions to fill with three blue, three green, and three red balls. We can fill three of the nine positions with blue balls in $\binom{9}{3}$ ways, three of the remaining positions with green balls in $\binom{6}{3}$ ways, and the remaining three positions with red balls in $\binom{3}{3}$ ways. Hence, the number of distinguishable arrangements of three blue, three green, and three red balls is $$\binom{9}{3}\binom{6}{3}\binom{3}{3} = \frac{9!}{3!3!3!}$$ The factors of $3!$ in the denominator represent the number of ways balls of the same color can be permuted among themselves within a given arrangement since permuting balls of the same color among themselves does not produce an arrangement that is distinguishable from the given arrangement.

From these, we must exclude those arrangements in which there is at least one pair of adjacent balls of the same color.

A pair of adjacent balls of the same color: There are three ways to pick the color. We have eight objects to arrange, the block of two adjacent balls, the other ball of that color, and the other six balls. We have eight positions to fill.

Say the block consists of blue balls. Then we can fill three of those eight positions with green balls in $\binom{8}{3}$ ways, three of the remaining positions with red balls in $\binom{5}{3}$ ways, place the block in one of the two remaining positions in $2$ ways, and place the other blue ball in the final open position in one way. Hence, there are $$\binom{8}{3}\binom{5}{3}2! = \frac{8!}{3!3!}$$ such arrangements. Since there are three ways of selecting the color, there are $$\binom{3}{1}\frac{8!}{3!3!}$$ arrangements in which a pair of adjacent balls are of the same color.

Two pairs of adjacent balls of the same color: There are two cases.

Both pairs of adjacent balls are of the same color: This means that all three balls of that color are adjacent. Thus, we have seven objects to arrange, the block of three balls of the same color and the other six objects. Since there are three ways to select the color, the number of arrangements in which there are two pairs of adjacent balls of the same color is $$\binom{3}{1}\frac{7!}{3!3!}$$

Two colors in which there is a pair of adjacent balls of that color: There are $\binom{3}{2}$ ways to select the colors of the pairs. We have seven objects to arrange, the two blocks, the two single balls of those colors, and the three balls of the other color. Thus, there are $$\binom{3}{2}\frac{7!}{3!}$$ arrangements in which there are two colors in which there is a pair of adjacent balls of that color.

Three pairs of adjacent balls of the same color: There are again two cases.

Two pairs of adjacent balls of the same color and one pair of adjacent balls of a different color: There are three ways to pick the color in which there are two pairs of adjacent balls and two ways to pick the other color in which there is one pair of adjacent balls of that color. We have six objects to arrange, the block of three balls, the pair, the other ball of that color, and the three balls of the remaining color. Hence, there are $$\binom{3}{1}\binom{2}{1}\frac{6!}{3!}$$ arrangements of this type.

Three colors in which there is a pair of adjacent balls of that color: We have six objects to arrange, the three blocks and the three individual balls. Since the objects are all distinct, there are $$6!$$ arrangements of this type.

Four pairs of adjacent balls of the same color: We again have two cases.

Two colors in which there are two pairs of adjacent balls of that color: There are $\binom{3}{2}$ ways to select the two colors. We have five objects to arrange, the two blocks of three adjacent balls of the same color and the three balls of the third color. Hence, there are $$\binom{3}{2}\frac{5!}{3!}$$ arrangements of this type.

One color in which there are two pairs of adjacent balls of that color and two other colors in which there is one pair of adjacent balls of that color: There are three ways to select the color with two pairs of adjacent balls of that color. We have five objects to arrange, the block of three balls, the two blocks of two balls, and the other two balls. Since the five objects are distinct, there are $$\binom{3}{1}5!$$ arrangements of this type.

Five pairs of adjacent balls of the same color: There must be two colors in which there are two pairs of adjacent balls of that color and there must also be a pair of adjacent balls of the third color. There are $\binom{3}{2}$ ways of selecting the two colors in which there are two pairs of adjacent balls of that color. We have four objects to arrange, the two blocks of three balls, the block of two balls, and the other ball of that color. Since the objects are distinct, there are $$\binom{3}{2}4!$$ arrangements of this type.

Six pairs of adjacent balls of the same color: There must be two pairs of adjacent balls of the same color in each of the three colors. Hence, we have three objects to arrange, a block of three blue balls, a block of three green balls, and a block of three red balls. Since these objects are distinct, there are $$3!$$ arrangements of this type.

By the Inclusion-Exclusion Principle, the number of distinguishable arrangements of three blue, three green, and three red balls in which no two balls of the same color are adjacent is $$\frac{9!}{3!3!3!} - \binom{3}{1}\frac{8!}{3!3!} + \binom{3}{1}\frac{7!}{3!3!} + \binom{3}{2}\frac{7!}{3!} - \binom{3}{1}\binom{2}{1}\frac{6!}{3!} - 6! + \binom{3}{2}\frac{5!}{3!} + \binom{3}{1}5! - \binom{3}{2}4! + 3!$$

This brings us to the question of symmetry. Notice that none of these $174$ arrangements can be a palindrome since for the two colors that do not occupy the middle position, there must be an odd number of balls of that color on one side of the middle ball and an even number of balls of that color on the other side of the middle ball. If we equate two arrangements that can be obtained through reflection, we are left with $87$ distinguishable arrangements of the balls.

$\endgroup$
  • 1
    $\begingroup$ Amazing solution! So analytic and explanatory!! Thank you very much! $\endgroup$ – Alex.vollenga Dec 17 '17 at 14:42
0
$\begingroup$

Hint: Try to find the value for the complement problem, that will be more easier and then subtract it from all possibility to get your reqd value.

Complement Problem: Sequence where there is atleast one place where there is two consecutive balls of same colour.

$\endgroup$
  • $\begingroup$ I think I found 174, which by symmetry must be 87? $\endgroup$ – Alex.vollenga Dec 16 '17 at 17:18
  • $\begingroup$ The complement problem is not really any easier here. It is the problem as stated that is easier, if anything. $\endgroup$ – ShreevatsaR Jan 31 '18 at 3:51
0
$\begingroup$

There are 9 places to fill and the statement will be sufficed when alternate colours aren't the same so we have 3 options to fill the first (i.e. red, green or blue) 2 options to fill the second (i.e the remaining two colours) and only one to fill the next and then same 2 (as it cant be the previous ball), 2 again , 1 and then same 2, 2, 1. so the answer will be 3x2x1x2x2x1x9x2x1=96

$\endgroup$
  • 1
    $\begingroup$ Hi and welcome to the Math.SE. Producing beautiful and beautifully formatted text is one of the points that makes an answer good: if you want to learn how to do this, please have a look at MathJax basic tutorial and quick reference. $\endgroup$ – Daniele Tampieri Jan 16 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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