How many nine-digit sequences with exactly three 0s, three 1s, and three 2s can be created if there are never three consecutive numbers that are the same?
Can someone please show a step-by-step explanation? I'm currently studying for my final examination but this question has confused me.
My attempt at a solution:
Without restrictions, there are $\dfrac{9!}{3!3!3!}$ possible arrangements (divided by three $3!$ to account for the repetition).
There are two possible cases where the digits could be consecutive:
-
Only one of the three digits are consecutive.
"Glue" the three of the same number together (e.g., $000$) and count it as one possible placeholder in the 7 positions (no longer 9 because we have glued some digits together).
There are $3\choose 1$ way to choose which number to glue together. Choose its position in $7\choose 1$ way and distribute the remaining digits in $\dfrac{6!}{3!3!}$ ways. Multiply these together by the product rule.
-
All digits are consecutive.
An example of this is $000111222$. Gluing each number to itself, it is just like distributing 3 different numbers ($000, 111,$ and $222$) in to 3 positions: $3!$.
The above cases are mutually exclusive and by the sum rule can be added together. To calculate the case where are never three consecutive numbers, subtract these possibilities from the case without restrictions so the final answer is:
$${3\choose 1} \times {7\choose 1} \times \dfrac{6!}{3!3!} + 3! = 426$$
$$\dfrac{9!}{3!3!3!} – 426 = 1680$$
I'm not sure if I should subtract 4 from case 1 before adding the cases together: there are four possible cases where the string of three consecutive digits is at the beginning or the end. For example, if $000$ is consecutive:
- $000111222$
- $000222111$
- $111222000$
- $222111000$
The above cases are already included in case 2 (so if I do not subtract them, I believe this would over-count).
Best Answer
I think you would do better to use inclusion/exclusion.
If all the $0$s are consecutive, "glue" them like you said. You have $1+3+3$ items and the number of arrangements is $$\frac{7!}{1!\,3!\,3!}\ .$$ Same for $1$s, same for $2$s. If all the $0$s are consecutive and all the $1$s are consecutive, a similar argument gives $$\frac{5!}{1!\,1!\,3!}\ .$$ Likewise for $0$s and $2$s, likewise for $1$s and $2$s. If all three digits occur in blocks of $3$ there are $3!$ possibilities. By inclusion/exclusion, your final answer will be $$\frac{9!}{3!\,3!\,3!}-3\times\frac{7!}{1!\,3!\,3!}+3\times\frac{5!}{1!\,1!\,3!} -3!\ .$$