There are 5 different red balls,5 different green balls,5 different blue balls and 5 different black balls.In how many ways can they be arranged so that no two balls of same color are adjacent ?

This discussion board is a place to discuss our Daily Challenges and the math and science
related to those challenges. Explanations are more than just a solution — they should
explain the steps and thinking strategies that you used to obtain the solution. Comments
should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .

Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.

Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold

- bulleted - list

bulleted

list

1. numbered 2. list

numbered

list

Note: you must add a full line of space before and after lists for them to show up correctly

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.

Wow. That's a lot more complex than I was anticipating!

Rushi R.: Did you have a specific application in mind for this problem? Did it come from somewhere? Or did you just make it up and have trouble solving it yourself? The solution we have so far does not suggest the problem would be appropriate for a contest, which is kind of where I was assuming it came from.

My maths teacher is just absolutely good at creating tough questions.Accidentally, he gave us this question to solve.But,later when he tried to solve this question, he did the same mistake as everyone else..

Another way of explaining the inversion would be to use the technique Principle of Inclusion and Exclusion, which would be more familiar. Of course, these approaches use the same underlying ideas, which also explains why the resultant formula looks so similar to the general case of PIE.

@Mark Hennings
–
Choosing the 'correct' interpretation is extremely useful in this question. PIE is meant to be applied to events that are easily counted, and in this case considering them as distinct balls makes it easier to motivate the approach. (Note: For those who are wondering about the above comment, the 'multi-dimensional version' ends up being required because we need to account for the different colors having consecutive balls. If the question was simply about having no consecutive red balls, then we could apply PIE directly.)

So, let the 5 red balls be labelled $R_i$ (same for the other colors), and we will remember to account for the double counting by dividing out by $(5!) ^ 4$. Create the events $R_{i,j}$ which indicates that the $R_i$ and $R_j$ balls are next to each other (and same for the other colors). We are interested in finding (the complement of) $\cup R_{i,j}$, and to do this we apply PIE directly.

For example, the set of single events works out to having (at least) 1 pair of same colored balls next to each other. After accounting for the double counting, you will see that this correlates to your formula with values $a+b+c+d = 5$.

The set of double events works out to having (at least) 2 pairs of same colored balls next to each other. This gets slightly complicated, as it could be 2 different colors, the same color but distinct sets of balls, the same color but 1 repeated ball. After accounting for the double counting, you can see that this correlates with having $a+b+c+d = 6$.

Continuing on in this way, the set of $n$ events correlates with having $a+b+c+d = n +4$. This is slightly tricky to consider, but bear in mind that there are sets of 3 events with 0 outcomes, like $R_{1,2} \cup R_{2,3} \cup R_{1,3}$, since we can't have all 3 balls being next to each other. In fact, the only way that $n$ events do not lead to 0 outcomes, is to have the colored events 'chain up', where $R_{1,2} \cup R_{2,3} \cup R_{3,4}$ corresponds to having 4 consecutive red balls.

Hence, in this way, we are able to get at your final formula, without requiring the generating function argument. $_\square$

As I pointed out earlier, the generating function argument is actually PIE in disguise. Those who are interested should figure out how and why it works, and compare it to the Mobius transform in Number Theory.

(As a side note, in your final formula, if you used the substitution $a = a-1$ and $p = p-1$, then the equations will appear nicer, and the formulas above will not need the constant 4.)

@Calvin Lin
–
I think that both our methods are pretty much equally delicate; both have their elegancies and their clumsinesses. You have to work quite hard to break up your sum over the possibilities as a sum over four variables, and there is quite a lot of detail you have omitted. I think that honours are even, really! While the generating function technique, the PIE and the Binomial inversion formula are all equivalent in this case, there are plenty of cases where the generating function technique will succeed when the others will not.

If I make the substitutions you suggest, then my binomial coefficients become simpler, but my multinomial coefficient becomes more complex (it collects the $1$s and $4$s), and the formula is then for $N(p+1,q+1,r+1,s+1)$. A matter of swings and roundabouts.

My knowledge of matrices is minimal, but I'm very interested in what your formula is "saying" on an intuitive level. What concepts is it expressing, and why does it work?

Do some of the matrix multiplication first, to make things simpler. We are looking at
$\mathbf{a}^\mathsf{T}A^{19}\mathbf{b} \; = \; \left( \begin{array}{cccc}w & x & y & z\end{array}\right) \left(\begin{array}{cccc}0 & x & y & z \\ w & 0 & y & z \\ w & x & 0 & z \\ w & x & y & 0 \end{array}\right)^{19}\left(\begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \end{array}\right)$
If we consider the row vector $\mathbf{a}^\mathsf{T}A^{n-1}$ for any positive integer $n$, we see that all four terms in the vector are sums of monomials in $w,x,y,z$ of order $n$. The effect of the matrix multiplication by $A$ is that none of the monomials has $w$ followed directly by $w$, $x$ followed directly by $x$, $y$ followed directly by $y$ or $z$ followed directly by $z$. The monomials in the first term in $\mathbf{a}^\mathsf{T}A^{n-1}$ all end in $w$. Those in the second term all end in $x$, those in the third term all end in $y$ and those in the fourth term all end in $z$. At least, all of this is true if we do not perform any algebra like identifying $xyx$ with $x^2y$.

Thus, if we look at $\mathbf{a}^\mathsf{T}A^{19}\mathbf{b}$, we are simply adding together all the monomials in $\mathbf{a}^\mathsf{T}A^{19}$, and so we have the sum of all monomials of order $20$ which never contain the same variable repeated consecutively. If we now use algebra to identify like terms and collect them together, we end up with a homogeneous polynomial of degree $20$ in $w,x,y,z$, where the coefficient of $w^ax^by^cz^d$ is the number of monomials in four variables of order $20$ which contain $a$ copies of $w$, $b$ copies of $x$, $c$ copies of $y$ and $d$ copies of $z$ and which, moreover, have no variable repeated consecutively. In other words, the coefficient of $w^ax^by^cz^d$ is $N(a,b,c,d)$.

This formula enables a computer to sort the $4\times3^{19}$ sequences of length $20$ of four colours which contain no consecutively repeated colours, and pick out the coefficient $N(5,5,5,5)$ (and others). In computational terms, however, the formula effectively requires us to calculate all $4.6$ billion monomials, only to throw most of them away. The computation time for $N(5,5,5,5)$ using this method is quite big.

Theoretical considerations are fine but nothing beats trying the code. It only takes around 5 seconds even on my old machine with Mathematica.

The multivariable polynomial is only 891 terms and is not exactly wasted information. Solutions to every possible problem where the number of balls is 20 have been generated.

For small problems like this one it is feasible and on hand so I used it.

@Mark Hennings
–
Great explanation! We are working in a non-commutative algebra, which is why $xyx \neq x^2 y$. This allows us to store the order in which the letters appear.

The middle matrix represents a transition matrix where we can only move on to a distinct letter, and hence we are guaranteed to have "no two consecutive letters" that are the same. We raise it to the power 19 since we want to have 19 pairs of consecutive letters, which gives a total of 20. The initial and final vector (matrices) then allows us to count the number of sequences which start with $w$ or $x$ or $y$ or $z$.

This was given to me by a mathematician on the SE in the past. I am afraid it is a little bit too much for me. It looks like a matrix shorthand for a generating function since it generates all the solutions like a gf does.

There is also a recurrence equation but I did not get that either.I seemed to have caused confusion and controversy with that idea. My intent was only to corroborate Mark and Gopinath's answers. I apologize.

Please look at my reply to Christopher. The great John von Neumann once said that in math we do not understand things we just get used to them. He was probably joking but it actually is true in my case. I can use the method, understanding like love comes later ( hopefully ).

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.

You have considered a case where between any two red balls there is always a green ball....There are several cases where there is no green ball between two red balls..Please reply soon..I need your help.

@Lokesh Sharma
–
You either start with a red or green ball (factor 2) then the rest of the colours is fixed. Only thing to add is $5!^2$ for the orders of the different reds and the different greens.

@Ton de Moree
–
Thanks, you opened my eyes. I was rather using $5!*6!$ to computer the number of ways for arranging red and green balls. Now I am getting the same answer as yours.

Yeah, I see. The above solution is wrong. Anyway, I tried finding the answer using Python and I found out the answer is very much close to $\frac{5!*5!*2*16!}{6!}*35$.

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in`\(`

...`\)`

or`\[`

...`\]`

to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestI 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.

Log in to reply

Hi Mark,

Super! Your formula matches with the computer counted values for first few terms. Also, I think we can extend it for more colours.

N(p,q,r) matches with A110706, but does not have your formula.

Perhaps Dr. Zeilberger may be knowing whether a closed form exists or not.

Log in to reply

Wow. That's a lot more complex than I was anticipating!

Rushi R.: Did you have a specific application in mind for this problem? Did it come from somewhere? Or did you just make it up and have trouble solving it yourself? The solution we have so far does not suggest the problem would be appropriate for a contest, which is kind of where I was assuming it came from.

Log in to reply

My maths teacher is just absolutely good at creating tough questions.Accidentally, he gave us this question to solve.But,later when he tried to solve this question, he did the same mistake as everyone else..

Log in to reply

This looks good.

Another way of explaining the inversion would be to use the technique Principle of Inclusion and Exclusion, which would be more familiar. Of course, these approaches use the same underlying ideas, which also explains why the resultant formula looks so similar to the general case of PIE.

Log in to reply

If the Inclusion-Exlcusion Principle is to be used, we need some multi-dimensional version of it. I would be interested to see that expressed...

Log in to reply

So, let the 5 red balls be labelled $R_i$ (same for the other colors), and we will remember to account for the double counting by dividing out by $(5!) ^ 4$. Create the events $R_{i,j}$ which indicates that the $R_i$ and $R_j$ balls are next to each other (and same for the other colors). We are interested in finding (the complement of) $\cup R_{i,j}$, and to do this we apply PIE directly.

For example, the set of single events works out to having (at least) 1 pair of same colored balls next to each other. After accounting for the double counting, you will see that this correlates to your formula with values $a+b+c+d = 5$.

The set of double events works out to having (at least) 2 pairs of same colored balls next to each other. This gets slightly complicated, as it could be 2 different colors, the same color but distinct sets of balls, the same color but 1 repeated ball. After accounting for the double counting, you can see that this correlates with having $a+b+c+d = 6$.

Continuing on in this way, the set of $n$ events correlates with having $a+b+c+d = n +4$. This is slightly tricky to consider, but bear in mind that there are sets of 3 events with 0 outcomes, like $R_{1,2} \cup R_{2,3} \cup R_{1,3}$, since we can't have all 3 balls being next to each other. In fact, the only way that $n$ events do not lead to 0 outcomes, is to have the colored events 'chain up', where $R_{1,2} \cup R_{2,3} \cup R_{3,4}$ corresponds to having 4 consecutive red balls.

Hence, in this way, we are able to get at your final formula, without requiring the generating function argument. $_\square$

As I pointed out earlier, the generating function argument is actually PIE in disguise. Those who are interested should figure out how and why it works, and compare it to the Mobius transform in Number Theory.

(As a side note, in your final formula, if you used the substitution $a = a-1$ and $p = p-1$, then the equations will appear nicer, and the formulas above will not need the constant 4.)

Log in to reply

If I make the substitutions you suggest, then my binomial coefficients become simpler, but my multinomial coefficient becomes more complex (it collects the $1$s and $4$s), and the formula is then for $N(p+1,q+1,r+1,s+1)$. A matter of swings and roundabouts.

Log in to reply

I was just waiting for your answer....Thanks..

Log in to reply

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.

Log in to reply

My knowledge of matrices is minimal, but I'm very interested in what your formula is "saying" on an intuitive level. What concepts is it expressing, and why does it work?

Log in to reply

Do some of the matrix multiplication first, to make things simpler. We are looking at $\mathbf{a}^\mathsf{T}A^{19}\mathbf{b} \; = \; \left( \begin{array}{cccc}w & x & y & z\end{array}\right) \left(\begin{array}{cccc}0 & x & y & z \\ w & 0 & y & z \\ w & x & 0 & z \\ w & x & y & 0 \end{array}\right)^{19}\left(\begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \end{array}\right)$ If we consider the row vector $\mathbf{a}^\mathsf{T}A^{n-1}$ for any positive integer $n$, we see that all four terms in the vector are sums of monomials in $w,x,y,z$ of order $n$. The effect of the matrix multiplication by $A$ is that none of the monomials has $w$ followed directly by $w$, $x$ followed directly by $x$, $y$ followed directly by $y$ or $z$ followed directly by $z$. The monomials in the first term in $\mathbf{a}^\mathsf{T}A^{n-1}$ all end in $w$. Those in the second term all end in $x$, those in the third term all end in $y$ and those in the fourth term all end in $z$. At least, all of this is true if we do not perform any algebra like identifying $xyx$ with $x^2y$.

Thus, if we look at $\mathbf{a}^\mathsf{T}A^{19}\mathbf{b}$, we are simply adding together all the monomials in $\mathbf{a}^\mathsf{T}A^{19}$, and so we have the sum of all monomials of order $20$ which never contain the same variable repeated consecutively. If we now use algebra to identify like terms and collect them together, we end up with a homogeneous polynomial of degree $20$ in $w,x,y,z$, where the coefficient of $w^ax^by^cz^d$ is the number of monomials in four variables of order $20$ which contain $a$ copies of $w$, $b$ copies of $x$, $c$ copies of $y$ and $d$ copies of $z$ and which, moreover, have no variable repeated consecutively. In other words, the coefficient of $w^ax^by^cz^d$ is $N(a,b,c,d)$.

This formula enables a computer to sort the $4\times3^{19}$ sequences of length $20$ of four colours which contain no consecutively repeated colours, and pick out the coefficient $N(5,5,5,5)$ (and others). In computational terms, however, the formula effectively requires us to calculate all $4.6$ billion monomials, only to throw most of them away. The computation time for $N(5,5,5,5)$ using this method is quite big.

Log in to reply

Theoretical considerations are fine but nothing beats trying the code. It only takes around 5 seconds even on my old machine with Mathematica.

The multivariable polynomial is only 891 terms and is not exactly wasted information. Solutions to every possible problem where the number of balls is 20 have been generated.

For small problems like this one it is feasible and on hand so I used it.

Log in to reply

$xyx \neq x^2 y$. This allows us to store the order in which the letters appear.

Great explanation! We are working in a non-commutative algebra, which is whyThe middle matrix represents a transition matrix where we can only move on to a distinct letter, and hence we are guaranteed to have "no two consecutive letters" that are the same. We raise it to the power 19 since we want to have 19 pairs of consecutive letters, which gives a total of 20. The initial and final vector (matrices) then allows us to count the number of sequences which start with $w$ or $x$ or $y$ or $z$.

Log in to reply

Hi;

This was given to me by a mathematician on the SE in the past. I am afraid it is a little bit too much for me. It looks like a matrix shorthand for a generating function since it generates all the solutions like a gf does.

There is also a recurrence equation but I did not get that either.I seemed to have caused confusion and controversy with that idea. My intent was only to corroborate Mark and Gopinath's answers. I apologize.

Log in to reply

Please Explain..I am very interested in what you did ..

Log in to reply

Hi;

Please look at my reply to Christopher. The great John von Neumann once said that in math we do not understand things we just get used to them. He was probably joking but it actually is true in my case. I can use the method, understanding like love comes later ( hopefully ).

Log in to reply

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.

Log in to reply

You have considered a case where between any two red balls there is always a green ball....There are several cases where there is no green ball between two red balls..Please reply soon..I need your help.

Log in to reply

Hmm, indeed!

My first though was to fix that by adding a factor $4!$ to account for the order of the colours, but that doesn't work either.

I'm trying to think of another way, but most involve spererating several cases, which is something we don't want to do with this amount of balls...

Log in to reply

$5!*5!*2$ number of ways to do that. How?

When you arranged red and green balls in the first place, you said there areLog in to reply

$5!^2$ for the orders of the different reds and the different greens.

You either start with a red or green ball (factor 2) then the rest of the colours is fixed. Only thing to add isLog in to reply

$5!*6!$ to computer the number of ways for arranging red and green balls. Now I am getting the same answer as yours.

Thanks, you opened my eyes. I was rather usingLog in to reply

Using the fact that if there are $n$ places than $r$ things can be arranged in $nPr$ no of ways -Total no of ways = $16!*5!$[

EDIT: The total number of ways are $\frac{5!*5!*2*16!}{6!}$ as number of ways to arrangered and green balls is$5!*5!*2$not$5!*6!$]Log in to reply

You got the same problem as Ton D...

Log in to reply

Yeah, I see. The above solution is wrong. Anyway, I tried finding the answer using Python and I found out the answer is very much close to $\frac{5!*5!*2*16!}{6!}*35$.

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Is the answer 7,46,496?

Log in to reply

I am sorry I don't have the answer..

Log in to reply

20*15^19

Log in to reply

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)Log in to reply

20

1514131212111099876654332*1Log in to reply

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

Log in to reply

Is the answer 80?

Log in to reply

No..The answer can not be that less..

Log in to reply

Following ton d select any two arrange them n then put the others btw the gaps n multiply by 2.

Log in to reply