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

combinationscombinatoricscontest-mathdynamic programming

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?

Best Answer

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

Related Question