8
$\begingroup$

A bag contains $2$ red, $2$ green, $2$ black, $3$ white, $1$ yellow, $1$ brown and $1$ orange ball.

In how many ways the balls be arranged in a row by taking all of them together if balls of same color cannot be placed adjacent?

I am aware that $\dfrac{12!}{2!\times 2! \times 2! \times 3!}$ arrangements are possible. But these arrangements contain balls of same colors placed adjacent also. How to solve this problem?

$\endgroup$
  • $\begingroup$ Are the balls of the same color distinguishable from each other? $\endgroup$ – Antoni Parellada Jan 16 '17 at 19:03
  • $\begingroup$ balls of same color are identical. $\endgroup$ – jvm Jan 16 '17 at 19:06
  • $\begingroup$ answer is $3301200$ $\endgroup$ – Kiran Jan 16 '17 at 19:08
  • 1
    $\begingroup$ @Kiran Any explanation for this result ? Just posting a number doesn´t help. $\endgroup$ – callculus Jan 16 '17 at 19:15
  • 1
    $\begingroup$ @Kiran Not really. When I read the exercise I had the feeling that the calculations would be excessive. You have made it this way. But it is hard to comprehend. I only can hope that what you did is right. $\endgroup$ – callculus Jan 16 '17 at 19:42
3
$\begingroup$

This answer is based upon a generating function of generalized Laguerre polynomials \begin{align*} L_k^{(\alpha)}(t)=\sum_{i=0}^k(-1)^k\binom{k+\alpha}{k-i}\frac{t^i}{i!}\tag{1} \end{align*}

The Laguerre polynomials have some remarkable combinatorial properties and one of them is precisely suited to answer problems of this kind. This is nicely presented in Counting words with Laguerre series by Jair Taylor.

We encode the colors (r)ed, (g)reen, (b)lack, (w)hite, (y)ellow, (B)rown, (o)range of the balls with the letters \begin{align*} \{r,g,b,w,y,B,o\} \end{align*} and are looking for words of length $12$ built from \begin{align*} r,r,g,g,b,b,w,w,w,y,B,o \end{align*} which have the property that they contain no consecutive equal letters. These words are called Carlitz words or Smirnov words.

We find in section 2 of the referred paper Laguerre polynomials $l_k(t)$ defined by their generating function \begin{align*} \sum_{k=0}^\infty l_k(t)x^k=e^{\frac{tx}{1+x}} \end{align*} The first few such polynomials are \begin{align*} l_0(t)&=1\\ l_1(t)&=t\\ l_2(t)&=\frac{1}{2}t^2-t\\ l_3(t)&=\frac{1}{6}t^3-t^2+t\tag{2} \end{align*} These polynomials are a specific form of Laguerre polynomials (1), namely $$l_k(t)=(-1)^kL_k^{(-1)}(t)$$

Theorem 2.1 in the referred paper states: Given nonnegative integers $n_1,\ldots,n_k$, the number of $k$-ary Carlitz words with the letter $i$ used exactly $n_i$ times is \begin{align*} \int_{0}^\infty e^{-t}\left(\prod_{i=1}^kl_{n_i}(t)\right)\,dt\tag{3} \end{align*}

Since we have three characters $r,g,b$ each twice, one character $w$ three times and three characters $y,B,o$ each occurring once, we set \begin{align*} &n_1=n_2=n_3=2,\\ &n_4=3,\\ &n_5=n_6=n_7=1 \end{align*}

We apply theorem 2.1. and obtain using (2) and (3) and with some help of Wolfram Alpha \begin{align*} \int_{0}^\infty&e^{-t}\left(\prod_{i=1}^7l_{n_i}(t)\right)\,dt\\ &=\int_{0}^\infty e^{-t}\left(l_2(t)\right)^3l_3(t)\left(l_1(t)\right)^3\,dt\\ &=\int_{0}^\infty e^{-t}\left(\frac{1}{2}t^2-t\right)^3\left(\frac{1}{6}t^3-t^2+t\right)t^3\,dt\\ &=\int_{0}^\infty e^{-t}\left(\frac{1}{48}t^{12}-\frac{1}{4}t^{11}+\frac{9}{8}t^{10} -\frac{29}{12}t^9+\frac{5}{2}t^8-t^7\right)\,dt\\ &=3301200 \end{align*}

$\endgroup$
  • $\begingroup$ Great! This problem seems painfully ad hoc, and I am very pleased to see that there is an analytic solution. $\endgroup$ – Antoni Parellada Jan 17 '17 at 13:09
  • $\begingroup$ @AntoniParellada: I agree! It was also great for me to see the combinatorial power of these polynomials. Another powerful method the cluster method by Goulden-Jackson could also be applied here (with somewhat more effort). It is presented in this answer. $\endgroup$ – Markus Scheuer Jan 17 '17 at 13:17
  • 1
    $\begingroup$ I went down the proverbial rabbit hole, fully knowing that I was getting in trouble, but the pain of not getting anywhere certainly gave me an appreciation for your contribution! $\endgroup$ – Antoni Parellada Jan 17 '17 at 13:19
1
$\begingroup$

This question is equivalent to

"In how many different ways can we arrange letters of the word AABBCCDDDEFG such that no two adjacent letters are alike?"

I have been doing many such questions in past. This tool was very useful. Following is the result obtained from this tool.
[see generated question $24$. Thought of retying it here. but as i said in my comment, it is very long and pasting the screenshot here]

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Good work! (+1) I've added an answer which confirms your result. $\endgroup$ – Markus Scheuer Jan 17 '17 at 11:37

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.