# what is the formula to calculate the permutations

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 ?

• what does mean BLUE balls never come together?i think it means that in each ball there is 1 blue only right? – dato datuashvili Apr 30 '12 at 8:24
• sorry in each box i meant – dato datuashvili Apr 30 '12 at 8:30
• each box can contain only 1 ball. BLUE balls never come together means no two adjacent boxes can contain blue balls. – ANKIT Apr 30 '12 at 8:36
• This question has been recently asked and answered on MSE. – 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. ;)