Permutation Problem! Need some experts.

I think this is right, but it needs checking... Some of the formulae are very long, so you may need to scroll to read this.

I am assuming that the red balls are indistinguishable from each other, and similarly for the green, blue and black balls. If you want to be able to tell the red (green, blue, black) balls apart, multiply by $5!^4$.

For any $a,b,c,d \ge 1$, let $N(a,b,c,d)$ be the number of orderings of $a$ red balls, $b$ green balls, $c$ blue balls and $d$ black balls for which no two consecutive balls are the same colour.

There are $\frac{(a+b+c+d)!}{a!b!c!d!}$ orderings of $a$ red balls, $b$ green balls, $c$ blue balls and $d$ black balls altogether. For any of these orderings the red balls will occur in some number $\alpha$ (where $1 \le \alpha \le a$) of sequences of consecutive reds. The number of ways in which the $a$ red balls can be distributed amongst $\alpha$ sequences of consecutive reds is just equal to the number of ordered partitions of $a$ which have $\alpha$ elements, namely ${a-1 \choose \alpha-1}$. If the $b$ green balls come in $\beta$ sequences of consecutive greens, the $c$ blue balls come in $\gamma$ sequences of consecutive blues, and the $d$ black balls come in $\delta$ sequences of consecutive blacks, then there are ${b-1 \choose \beta-1}$ ways of distributing the green balls amongst the $\beta$ sequences, ${c-1 \choose \gamma-1}$ ways of distributing the blue balls amongst the $\gamma$ sequences, and ${d-1\choose \delta-1}$ ways of distributing the black balls amongst the $\delta$ sequences. Moreover there are $N(\alpha,\beta,\gamma,\delta)$ ways in which the sequences can be ordered so that no two sequences of the same colour are next to each other (in which case they would join in to a single sequence), and this leads us to the fairly daunting formula: $\frac{(a+b+c+d)!}{a!b!c!d!} \; = \; \sum_{\alpha=1}^a \sum_{\beta=1}^b \sum_{\gamma=1}^c \sum_{\delta=1}^d N(\alpha,\beta,\gamma,\delta){a-1 \choose \alpha-1}{b-1\choose \beta-1}{c-1 \choose \gamma-1}{d-1 \choose \delta-1}$ We need to invert this formula to calculate $N(a,b,c,d)$. Introduce the generating function $F(A,B,C,D) \; = \; \sum_{\alpha,\beta,\gamma,\delta=1}^\infty \frac{N(\alpha,\beta,\gamma,\delta)}{(\alpha-1)!(\beta-1)!(\gamma-1)!(\delta-1)!}A^\alpha B^\beta C^\gamma D^\delta$ Then $\begin{array}{rcl} e^{A+B+C+D}F(A,B,C,D) & = & \displaystyle\left(\sum_{p,q,r,s=0}^\infty \frac{A^pB^qC^rD^s}{p!q!r!s!}\right)\left(\sum_{\alpha,\beta,\gamma,\delta=1}^\infty \frac{N(\alpha ,\beta,\gamma, \delta)}{(\alpha-1)!(\beta-1)!(\gamma-1)!(\delta-1)!}A^\alpha B^\beta C^\gamma D^\delta \right) \\ & = & \displaystyle\sum_{{p,q,r,s \ge 0}\atop{\alpha,\beta,\gamma,\delta\ge1}} \frac{N(\alpha,\beta,\gamma,\delta)}{p!q!r!s!(\alpha-1)!(\beta-1)!(\gamma-1)!(\delta-1)!}A^{p+\alpha}B^{q+\beta}C^{r+\gamma}D^{s+\delta} \\ & = & \displaystyle\sum_{a,b,c,d \ge1}\frac{\left(\sum_{\alpha=1}^a \sum_{\beta=1}^b \sum_{\gamma=1}^c \sum_{\delta=1}^d N(\alpha,\beta,\gamma,\delta){a-1 \choose \alpha-1}{b-1\choose \beta-1}{c-1 \choose \gamma-1}{d-1 \choose \delta-1}\right)}{(a-1)!(b-1)!(c-1)!(d-1)!} A^aB^bC^cD^d \\ & = & \displaystyle\sum_{a,b,c,d \ge 1} \frac{(a+b+c+d)!}{a!b!c!d!(a-1)!(b-1)!(c-1)!(d-1)!}A^aB^bC^cD^d \end{array}$ and so $F(A,B,C,D) \; = \; e^{-(A+B+C+D)}\left(\sum_{a,b,c,d \ge 1} \frac{(a+b+c+d)!}{a!b!c!d!(a-1)!(b-1)!(c-1)!(d-1)!}A^aB^bC^cD^d\right)$ and a similar calculation to the one above shows that $F(A,B,C,D) \; = \; \sum_{p,q,r,s\ge1}\frac{\sum_{a=1}^{p}\sum_{b=1}^{q}\sum_{c=1}^{r}\sum_{d=1}^{s} (-1)^{p+q+r+s-a-b-c-d}\frac{(a+b+c+d)!}{a!b!c!d!}{p-1 \choose a-1}{q-1 \choose b-1}{r-1 \choose c-1}{s-1 \choose d-1}}{(p-1)!(q-1)!(r-1)!(s-1)!}A^pB^qC^rD^s$ which gives us $N(p,q,r,s) \; = \; \sum_{a=1}^{p}\sum_{b=1}^{q}\sum_{c=1}^{r}\sum_{d=1}^{s} (-1)^{p+q+r+s-a-b-c-d}\frac{(a+b+c+d)!}{a!b!c!d!}{p-1 \choose a-1}{q-1 \choose b-1}{r-1 \choose c-1}{s-1 \choose d-1}$ for $p,q,r,s \ge 1$. This is not a closed formula, but good enough for our purposes, since we only need to calculate $625$ terms to evaluate $N(5,5,5,5)$. Mathematica tells me that $N(5,5,5,5) = 134631576$. For comparison $\tfrac{20!}{5!\times5!\times5!\times5!} = 11732745024$.

It would be interesting if someone who knew more multinomial identities could evaluate the sum for $N(a,b,c,d)$.

N.B. Note that $N(a,b,c,d)$ is sometimes $0$ (for example $N(7,1,1,1)=0$), and this formula does give the right answer in those cases.

Hi;

Here is a nifty way to compute it but it will require a CAS to expand the expression.

The answer is

$\left (1,1,1,1 \right )\cdot\left( \begin{array}{cccc} w & 0 & 0 & 0 \\ 0 & x & 0 & 0 \\ 0 & 0 & y & 0 \\ 0 & 0 & 0 & z \\ \end{array} \right).\left(\left( \begin{array}{cccc} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \end{array} \right).\left( \begin{array}{cccc} w & 0 & 0 & 0 \\ 0 & x & 0 & 0 \\ 0 & 0 & y & 0 \\ 0 & 0 & 0 & z \\ \end{array} \right)\right)^{19}.\left( \begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \\ \end{array} \right)$

This will yield a large, large 4 variable polynomial. If you check the coefficient of

$w^5 x^5 y^5 z^5$

You will see the answer 134631576.

Here goes: Arrange the red and green balls first. There are $5!*5!*2$ ways to do this (do you see why?).

Now grabs the blue balls. Observe that there are 11 spaces to place one of them in the row of 10 red and green balls. We have to pick 5 of them, without repeating a space. This can be done in ${11}\choose{5}$ ways and $5!$ orders.

After this, grab the black balls. Observe that there are now 16 spaces to place one of them in the row of 15 red, gren and blue balls. We have to pick 5 of them, without repeating a space. This can be done in ${16}\choose{5}$ ways and $5!$ orders.

Thus in total we have $5!*5!*2*$${11}\choose{5}$$*5!*$${16}\choose{5}$$*5!$ ways of ordering the 20 balls.

That is over 8 trillion ways.

Using the fact that if there are $n$ places than $r$ things can be arranged in $nPr$ no of ways -

• Arranging red balls would account for $5P5$ or $5!$ ways.
• Arranging green balls given red balls are arranged in a particular way would result in $6P5$ or $6!$ no of ways.
• Arranging blue balls given the above balls are arranged in a particular way will give $11P5$ or $11!/6!$ no of ways.
• Now black balls can be arranged in $16P5$ or $16!/11!$

Total no of ways = $16!*5!$

[EDIT: The total number of ways are $\frac{5!*5!*2*16!}{6!}$ as number of ways to arrange red and green balls is $5!*5!*2$ not $5!*6!$]

Is the answer 7,46,496?

20*15^19

The following recurrence also looks good:

$f(p,q,r,s)=\left\{\begin{matrix} 0 & \text{if any of }p,q,r,s<0\\ 1 & \text{if any one of }p,q,r,s = 1 \text{ and others } 0\\ 2 & \text{if any two of }p,q,r,s = 1 \text{ and others } 0\\ 6 & \text{if any three of }p,q,r,s = 1 \text{ and the other's } 0\\ 24 & \text{if }p,q,r,s = 1 \\ f(p-1,q-1,r,s)+f(p-1,q,r-1,s)+f(p-1,q,r,s-1)+ & \\ f(p,q-1,r-1,s)+f(p,q-1,r,s-1)+f(p,q,r-1,s-1)+ & \\ 2\cdot \big(f(p,q-1,r-1,s-1) + f(p-1,q,r-1,s-1) + & \\ f(p-1,q-1,r,s-1) + f(p-1,q-1,r-1,s)\big) + & \\ 3\cdot f(p-1,q-1,r-1,s-1) & p,q,r,s > 1 \end{matrix}\right.$

In plaintext: f(p,q,r,s) = f(p-1,q-1,r,s)+f(p-1,q,r-1,s)+f(p-1,q,r,s-1)+f(p,q-1,r-1,s)+f(p,q-1,r,s-1)+f(p,q,r-1,s-1)+2(f(p,q-1,r-1,s-1) + f(p-1,q,r-1,s-1) + f(p-1,q-1,r,s-1) + f(p-1,q-1,r-1,s)) + 3f(p-1,q-1,r-1,s-1)

201514131212111099876654332*1

in how many ways can a person distribute 6 books among 3 people such that none get equal of books?

Is the answer 80?