1
$\begingroup$

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 ?

  • 0
    This question has been recently asked and [answered](http://math.stackexchange.com/questions/137577/number-of-combination-in-which-no-two-red-balls-are-adjacent) on MSE.2012-04-30

1 Answers 1

1

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. ;)

  • 0
    thanks @m_l this resolved my problem2012-04-30