I am new to the permutations. I have a problem with me for which I am not able to use proper formula -

Problem: There are X boxes in which balls need to be placed. The balls are of two colors - BLUE RED. We have unlimited balls of both colors. We need to find the number of permutations / ways in which the balls will be placed in the boxes in such a way that BLUE balls never come together.

Solution So far I have reached to the below formula- = (Total number of arrangements - Arrangements of BLUE balls sitting together) = (2^X - Arrangements of BLUE balls sitting together)

I am stuck for Arrangements of BLUE balls sitting together

What should be the right formula for this ?

  • $\begingroup$ what does mean BLUE balls never come together?i think it means that in each ball there is 1 blue only right? $\endgroup$ – dato datuashvili Apr 30 '12 at 8:24
  • $\begingroup$ sorry in each box i meant $\endgroup$ – dato datuashvili Apr 30 '12 at 8:30
  • $\begingroup$ each box can contain only 1 ball. BLUE balls never come together means no two adjacent boxes can contain blue balls. $\endgroup$ – ANKIT Apr 30 '12 at 8:36
  • $\begingroup$ This question has been recently asked and answered on MSE. $\endgroup$ – André Nicolas Apr 30 '12 at 11:12

Denote by $b(n)$ the number of arrangements on $n$ boxes such that at least two blue balls are neighbours (I'll call this a "bad" arrangement). I'm going for a recurrence relation.

Assume that we know $b(k)$ for $k < n$. Now consider the first box. If it contains a red ball, we have $b(n-1)$ combinations which complete this to a bad arrangement. If it contains a blue ball and the second box also contains a blue ball, the arrangement is bad no matter what the other boxes contain, so we have $2^{n-2}$ arrangements in this case. If the second box contains a red ball, we have $b(n-2)$ combinations which yield a bad arrangement.

So $b(n) = b(n-1) + b(n-2) + 2^{n-2}$. The initial values are $b(1) = 0$ and $b(2) = 1$. You should be able to find a closed form expression using methods described e.g. here, but right now I don't have the time to do it myself. ;)

  • $\begingroup$ thanks @m_l this resolved my problem $\endgroup$ – ANKIT Apr 30 '12 at 11:24

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.