Count the ways to divide 18 colored and numbered balls into 6 groups

Question

Consider a box has $18$ balls, $6$ white balls numbered $1$ to $6$, $6$ black balls numbered $1$ to $6$ and $6$ red balls numbered $1$ to $6$. We have to divide all $18$ balls into $6$ groups (groups are not numbered) such that each group consists of one white, one black and one red ball and difference of numbers on any two balls of same group is at most one. Find number of ways this division can be done.

Define a group $G_i$ such that it contain the $r_i$ ball (red ball which has number $i$ written on it). Similarly be can define $b_i$ and $w_i$ and let the sum of number of the balls in $G_i$ is $S_i$.

Obviously,

$3i-2\leq S_i \leq 3i+2$ and $\sum_{i=1}^6 S_i =63$

And then I took 6 cases when no of the $G_i$ has same numbered ball ( except red one i.e. $G_3$ can have $r_3,b_3,w_4$ but can't have $r_3,b_2,w_2$), when exactly one of $G_i$ have same numbered ball, and then so on.

My approach was similar to counting each and every cases and consumed a lot of time. Is there any better way to tackle this problem?

Answer 1

Let $a_n$ be the number of ways that $n$ white/black/red balls labelled from 1 to $n$ can be arranged in the described manner. We're asked to determine $a_6$.

Observations towards a solution. If you're stuck, share what you've tried:

• $a_1 = 1$, $a_2 = 4$ (Groups are not numbered).
• If $G_1$ (the group containing $r_1$) contains any #2 balls, then $G_2$ is uniquely determined and we can set these groups aside, and we get $a_{n-2}$ solutions for this $G_1$.
• If $G_1$ is just $\{ w_1, b_1, r_1 \}$, then set this group aside, and there are $a_{n-1}$ solutions.
• Hence, the recurrence relation is:

$a_n = a_{n-1} + 3 a_{n-2}$

Thus, $a_6 = 97$.

Answer 2

What you would like to learn is "dynamic programming".

---

Denote the number of ways by $d(6)$.

Let us consider more problems that are similar.

• Replacing $6$ by $5$ everywhere, we will have $d(5)$. That is the number of ways to divide $5$ white balls, $5$ black balls and $5$ red balls numbered $1$ to $5$ respectively into $5$ groups such that each group consists of one white, one black and one red ball and difference of numbers on any two balls of same group is at most one.
• Similarly, we define $d(4), d(3), d(2), d(1)$.

---

Consider the case of $6$.

There is one group that contains ball W$6$, which is shorthand for the white ball numbered 6. There are four cases for the other two balls in that group.

• They are B$6$ and R$6$.
  Setting aside W$6$, B$6$ and R$6$, we have $5$ white balls, $5$ black balls and $5$ red balls numbered $1$ to $5$ respectively that should be divided into $5$ such groups. We are in the case of $5$.
• They are B$6$ and R$5$.
  Consider the group that contains R$6$. The only white ball that can be in this group is W$5$ or W$6$. However, W$6$ has been put into the other group. So this group must contain W$5$.
  Similarly, this group must contain B$5$.
  Setting aside W$6$, B$6$, R$5$ and R$6$, W$5$, B$5$, we have $4$ white balls, $4$ black balls and $4$ red balls numbered $1$ to $4$ respectively. We are in the case of $4$.
• They are B$5$ and R$6$.
  Similarly to the case above, setting aside the balls used for these two groups, we are in the case of $4$.
• They are B$5$ and R$5$.
  The group that contain W$5$ must contain B$6$ and R$6$.
  Setting aside the balls for these two groups, we are in the case of $4$.

Combining the above cases, we have found that $$d(6)=d(5)+3d(4).$$

Similarly, we have $d(5)=d(4)+3d(3)$, $\ d(4)=d(3)+3d(2)$, $\ d(3)=d(2)+3d(1)$. These formula are called the recurrence relations.

---

Since $d(1)=1$, $d(2)=4$, we have $d(3)=7$, then $d(4)=19$, then $d(5)=40$, then $d(6)=97.$

---

Here is an easy exercise.

Suppose besides the 18 balls, we also have $6$ green balls numbered $1$ to $6$. We have to divide all $24$ balls into $6$ groups such that each group consists of $4$ balls of different colors and the difference of numbers on any two balls of the same group is at most one. Find the number of ways.