2
$\begingroup$

There are 2 Red balls, 3 Blue balls, 4 Green balls, 2 Yellow balls. In how many ways can we place the balls in straight line such that no two identical balls (balls of the same color) are in adjacent position?

P.S.
So far I've got the following: *Total no of arrangements of balls = $$\frac{11!}{2!3!4!2!}$$ Now, I know that we need to use inclusion-exclusion principle to get the number of repeated entries. But, this is where I'm stuck.

Calculating the number of arrangements in which, say, there are just two red balls, is rather easy. i.e. $$\text{No of arrangements without identical adjacents} = \text{Total number of arrangements} − n(R \cup B \cup G \cup Y)$$ Where $n(R),n(B),n(G),n(Y)$ are the number of arrangements where R,B,G,Y correspondingly are repeated adjacently. I'm stuck on how to compute the number of arrangements in which, say, there are more than two red balls.

The number which I'm getting and the number of generated permutations in the below generator don't match.

Type rrbbbggggyy in the following site. Also uncheck the Allow adjacent equals check box. http://users.telenet.be/vdmoortel/dirk/Maths/permutations.html*

$\endgroup$
  • $\begingroup$ Are you stuck on what to include and exclude or how to compute the number of arrangements in which, say, there are two consecutive red balls? $\endgroup$ – N. F. Taussig Mar 21 '16 at 0:10
  • $\begingroup$ @N.F.Taussig Calculating the number of arrangements in which, say, there are just two red balls, is rather easy. $ i.e.No\:of\:arrangements\:without\:identical\:adjacents = Total\:number\:of\:arrangements - n(R \cup B \cup G \cup Y)$ . Where $n(R),n(B),n(G),n(Y)$ are the number of arrangements where R,B,G,Y correspondingly are repeated adjacently. I'm stuck on how to compute the number of arrangements in which, say, there are more than two red balls. $\endgroup$ – Vishnu Vivek Mar 21 '16 at 6:53
  • $\begingroup$ Can you explain the near-simultaneous appearance of your question with this question? In case this is due to an ongoing contest, please see our policy on that. $\endgroup$ – joriki Mar 21 '16 at 10:51
  • 1
    $\begingroup$ @joriki This was a question asked in a recent online programming interview last week. The interview has got over. I have figured out the programmatic solution for this using brute force. But I was just wondering if there is a mathematical solution. $\endgroup$ – Vishnu Vivek Mar 21 '16 at 15:41
2
$\begingroup$

Here's an ad hoc solution that doesn't generalize well to higher numbers of balls.

I'll treat balls of the same colour as distinguishable throughout and divide through by the number $4!3!2!2!$ of permutations of indistinguishable balls in the end.

Since it's the $4$ green balls that make inclusion-exclusion most cumbersome to apply, let's regard these as walls and distribute the remaining balls among them. If we have $k$ non-green objects, we can select one for each green ball in $\frac{k!}{(k-4)!}$ ways, glue the green balls to their right, and then permute the resulting $k$ objects in $k!$ ways. This doesn't allow a green ball to be on the very left, so we have to add a contribution where we select one of the $4$ green balls to be on the very left, select one object for each of the remaining $3$ green balls in $\frac{k!}{(k-3)!}$ ways and permute the resulting $k$ objects in $k!$ ways. Let's denote the total for $k$ objects by $g_k$:

$$ g_k=k!^2\left(\frac1{(k-4)!}+\frac4{(k-3)!}\right)\;, $$

where terms with negative factorials should be omitted.

Now we have $2$ red, $2$ yellow and $3$ blue balls to distribute. That yields $\binom22+\binom22+\binom32=5$ adjacency conditions to satisfy. Let's first ignore the complications from the interactions of the blue pairs and just perform inclusion-exclusion for these five conditions. This yields

$$ \sum_{k=0}^5(-1)^k\binom5ka_k\;, $$

where $a_k=2^kg_{7-k}$ is the number of arrangements that result when we glue $k$ pairs of the $7$ non-green balls together and the factor $2^k$ arises because each pair can be glued together in two different orders.

Now we have to account for the interactions of the blue pairs. First consider the cases including two blue adjacency conditions. These are in fact satisfiable, but we overcounted them, since there are only $2$ orders in which the blue balls can be glued together to satisfy two adjacency conditions, whereas we counted $4$, so we have to substract half of that contribution:

$$ \frac12\binom32\sum_{k=0}^2(-1)^{k+2}\binom2ka_{k+2}\;, $$

where $k$ now counts the non-blue adjacency conditions fulfilled.

That leaves the cases with all three blue pairs. These shouldn't have been counted at all, since it's impossible to have all three pairs of blue balls adjacent, so we need another subtraction of

$$ \sum_{k=0}^2(-1)^{k+3}\binom2ka_{k+3}\;. $$

Adding it all up yields

\begin{align} &a_0-5a_1+10a_2-10a_3+5a_4-a_5-\frac32\left(a_2-2a_3+a_4\right)+(a_3-2a_4+a_5)\\ ={}&a_0-5a_1+\frac{17}2a_2-6a_3+\frac32a_4\\ ={}&8467200-5\cdot1209600+\frac{17}2\cdot172800-6\cdot23040+\frac32\cdot2304\\ ={}&3753216\;, \end{align}

and dividing by $4!3!2!2!=576$ yields $6516$ admissible arrangements, in agreement with the calculation on the site you linked to.

$\endgroup$
  • 1
    $\begingroup$ I know it's late, but better late than never, thanks a lot @joriki !!! $\endgroup$ – Vishnu Vivek Jun 3 at 5:15
  • $\begingroup$ You're, welcome, @VishnuVivek :-) $\endgroup$ – joriki Jun 5 at 15:36

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.