Number of $6$-digit numbers made up of the digits $1$, $2$, and $3$ with no digit occurring $3$ or more times consecutively?

Question

Find the number of 6-digit numbers made up of the digits $1$, $2$, and $3$ that have no digit occur three or more times consecutively. (For example, $123123$ would count, but $123111$ would not.)

We know the total number of possibilities without the occurrence restriction is $3^6 = 729$.

In order to eliminate the possibilities that can't be used, I set a block of 3 numbers as my 3 consecutive digits block. This block would have 3 different combinations. I then split the number of eliminations into 2 cases: one where the block of 3 is in the front, and one where the block of 3 is in the middle.

For case 1: I computed $3\cdot 24$, with $3$ being the ways to change the block of 3, and $24$ being the number of ways to change the other 3 numbers while not having another block of 3 consecutive.

For case 2: I computed $3^4$, ignoring the restriction of case 1.

Summing the 2 cases, I got $72+ 3\cdot 81 = 315$, I then subtracted from $729$ and got $414$, which turns out to be incorrect. What am I doing wrong?

Answer 1

You are allowed to have pairs of consecutive numbers but no triplets. SO you may have $0,1,2$ or $3$ pairs of pairs of consecutive numbers.

If you have $k$ pairs of consecutive numbers and you consider pairs of consecutive numbers and sington nummbers to be "slots", you have $6 -k$ slots.

There are are ${6-k \choose k}$ to choose which of the $k$ of the $6-k$ slots will be consecutive pairs and which will be singletons.

Given that the slots (whether pair or singleton) may not have any consecutive values, you will have $3$ choices for value of the first slot, and $2$ for the remaining $6-k-1$ slots.

So there will be $\sum\limits_{k=0}^3 {6-k \choose k}3*2^{6-k -1} = 1*3^5 + 5*3*2^4 + 6*3*2^3 + 1*3*2^2 = 492$. ways to do this.

===== earlier but not as clear attempts ====

$aaaxyz$ is unacceptable and there are $3*3^3$ ways to do that.

$abbbxy$ is unacceptable and there are $3*2*3^2$ ways to do that.

$xabbby$ is unacceptable and there are $3*3*2*3$ ways to do that.

$[xyz]aaa$ where it is not the case where $x=y=z$ and $a \ne z$ is unacceptable. There are $3^3 -3$ ways to do $[x=y=z]$ where not $x=y=z$. There are $2$ ways to do $a \ne z$ and so there are $(3^3 - 3)*2$ ways to do this.

So, if I made no error, there are $3^6 - 3*3^3 - 3*2*3^2 - 3*3*2*3 - (3^3 - 3)*2 =492$.

====

Another way:

The number of ways to do is so that there are $0$ consectutive numbers is $3*2^5$ ($3$ choices for the first number and then there every succeeding number must be different that the preceding).

The number to ways to do it so that there is $1$ pair of consecutive numbers it that: there are $5$ spots the consecutive pair can be. There are $3$ options the first number can be and each succeeding must be different than the preceding: $5*3*2^4$.

The number of ways to do it so there are $2$ pairs of consecutive numbers is: There are $3$ ways to place these $2$ pairs so that they are adjacent (a block of $4$ slots) and there $3$ ways to place them so they are not adjacent ([aa]b[cc]d, [aa]bc[dd],a[bb]c[dd]). And there are $4$ groups of letters. So there are $6*3*2^3$ ways to have $2$ pairs of consectutive numbers.

The number of ways to do it with $3$ paris of consecutive numbers is $[aa][bb][cc]$. There are $3$ choices for $a$ and $2$ for $b$ and $2$ for $c$ or $3*2^2$.

So $3*2^5 + 5*3*2^4 + 6*3*2^3 + 3*2^2 = 492$.

===

And although tedious....:

$a.....$ 3 ways

Branch 1: $aab....$ $3*2$ ways.

Branch 2: $ab....$ $3*2$ ways.

Branch 11: $aabbc$ $3*2*2$ ways (we only care that $c \ne b$ we don't care if $c = a$).

Branch 12: $aabc$ $3*2*2$ ways

Branch 21: $abbc$ $3*2$ ways.

Brach 22: $abc$ 3*2*2$ ways.

Branch 111: $aabbcc$ $3*2^2$ ways (done)

Branch 121: $aabccd$ $3*2^3$ ways (done)

Branch 122: $aabcd$ $3*2^3$ ways

Branch 211: $abbccd$ $3*2^3$ ways (done)

Branch 212: $abbcd$ $3*2^3$ ways

Branch 221: $abccd$ $3*2^3$ ways

Branch 222: $abcd$ $3*2^3$ ways.

Braanch 1221: $aabcdd$ $3*2^3$ ways d(done)

Branch 1222: $aabcde$ $3*2^4$ ways (done)

Branch 2121: $abbcdd$ $3*2^3$ ways(done)

Brach 2122: $abbcde$ $3*2^4$ ways (done)

Branch 2211: $abccdd$ $3*2^3$ ways (done)

Branch 2212: $abccde$ $3*2^4$ ways (done)

Branch 2221: $abcdde$ $3*2^4$ ways.(done)

Branch 22221: $abcdee$ $3*2^4$ ways. (done)

Branch 22222: $abcdef$ $3*2^5$ ways. (done)

Answer 2

There are $3^6 = 729$ possible sequences. From these, we must subtract those in which three consecutive digits are the same.

Observe that a prohibited sequence must begin in one of the first four positions. Let $A_1, A_2, A_3, A_4$ be the set of outcomes in which three consecutive digits beginning in the first, second, third, and fourth positions, respectively, are the same.

The set of outcomes that violate the restriction is $A_1 \cup A_2 \cup A_3 \cup A_4$. By the Inclusion-Exclusion Principle, \begin{align*} |A_1 \cup A_2 \cup A_3 \cup A_4| & = |A_1| + |A_2| + |A_3| + |A_4|\\ & \quad - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_1 \cap A_4| - |A_2 \cap A_4| - |A_3 \cap A_4|\\ & \quad + |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_1 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_4|\\ & \quad - |A_1 \cap A_2 \cap A_3 \cap A_4| \end{align*}

$|A_1|$: There are three ways of selecting the number that occupies the first three positions and three ways of selecting the number that occupy each of the last three positions. Hence, $|A_1| = 3^4$. By symmetry, $$|A_1| = |A_2| = |A_3| = |A_4| = 3^4$$

$|A_1 \cap A_2|$: Since the first three and the second three positions overlap, the first four positions must be filled with the same number. There are three ways to select this number and three ways to fill each of the remaining two positions. Hence, $|A_1 \cap A_2| = 3^3$. By symmetry, $$|A_1 \cap A_2| = |A_2 \cap A_3| = |A_3 \cap A_4| = 3^3$$

$|A_1 \cap A_3|$: Since the first three and the third three positions overlap, the first five positions must be filled with the same number. There are three ways to select this number and three ways to fill the remaining position. Hence, $|A_1 \cap A_3| = 3^2$. By symmetry, $$|A_1 \cap A_3| = |A_2 \cap A_4| = 3^2$$

$|A_1 \cap A_4|$: Since the first three and last three positions do not overlap, the first three positions can be filled in three ways, as can the last three. Hence, $$|A_1 \cap A_4| = 3^2$$

$|A_1 \cap A_2 \cap A_3|$: Since these sets overlap, the first five positions must be filled with the same number. There are three ways to choose this number and three ways to fill the remaining position. Thus, $|A_1 \cap A_3 \cap A_3| = 3^2$. By symmetry, $$|A_1 \cap A_2 \cap A_3| = |A_2 \cap A_3 \cap A_4| = 3^2$$

$|A_1 \cap A_2 \cap A_4|$: Since the first three positions overlap with the second three and the second three positions overlap with the last three positions, all six positions must be the same. There are three ways to select the number that fills all six positions. Hence, $|A_1 \cap A_2 \cap A_4| = 3$. By symmetry, $$|A_1 \cap A_2 \cap A_4| = |A_1 \cap A_3 \cap A_4| = 3$$

$|A_1 \cap A_2 \cap A_3 \cap A_4|$: All six positions must be filled with the same number. Since there are three ways to select the number, $$|A_1 \cap A_2 \cap A_3 \cap A_4| = 3$$

By the Inclusion-Exclusion Principle, \begin{align*} |A_1 \cup A_2 \cup A_3 \cup A_4| & = 3^4 + 3^4 + 3^4 + 3^4\\ & \quad - 3^3 - 3^2 - 3^2 - 3^3 - 3^2 - 3^3\\ & \quad + 3^2 + 3 + 3 + 3^2\\ & \quad - 3\\ & = 237 \end{align*} Hence, there are $729 - 237 = 492$ admissible sequences.

Answer 3

Discussion of what's missing in your answer

There are four places a block of three can start in the number. $$\begin{matrix} (1): && d & d & d & \cdot & \cdot & \cdot \\ (2): && \cdot & d & d & d & \cdot & \cdot \\ (3): && \cdot & \cdot & d & d & d & \cdot \\ (4): && \cdot & \cdot & \cdot & d & d & d \\ \end{matrix}$$ You have only discussed the first two. Additionally, if we just count these four configurations, we overcount configurations where there are four, five, or six consecutive digits. For instance, $111111$ can only be generated one way, but it has been included in the counts for configurations (1), (2), (3), and (4), so has been quadruple-counted.

Corrected version of your answer

There are ten ways to have three (or more) consecutive digits: $$\begin{matrix} (1): && d & d & d & \cdot & \cdot & \cdot \\ (2): && \cdot & d & d & d & \cdot & \cdot \\ (3): && \cdot & \cdot & d & d & d & \cdot \\ (4): && \cdot & \cdot & \cdot & d & d & d \\ (5): && d & d & d & d & \cdot & \cdot \\ (6): && \cdot & d & d & d & d & \cdot \\ (7): && \cdot & \cdot & d & d & d & d \\ (8): && d & d & d & d & d & \cdot \\ (9): && \cdot & d & d & d & d & d \\ (10): && d & d & d & d & d & d \end{matrix} $$

We will proceed by inclusion-exclusion.

And then proceed as shown by N.F.Taussig's answer. (I was about half way through when he saved me having to finish it.)

A solution that avoids explicit inclusion-exclusion

From each string of six digits, $d_1 d_2 d_3 d_4 d_5 d_6$, let us construct a new string of length $5$ having an "s" in position $i$ if $d_i = d_{i+1}$ and an "n" if $d_i \neq d_{i+1}$, as $i$ ranges from $1$ to $5$. A digit occurring three or more times consecutively corresponds to two or more consecutive "s"s. There are only $3$ choices of first pairs of digits which produce an "s" in the first position and $6$ choices of pairs of digits which produce an "n" in the first position. Following an "s" only one choice of digit can produce an "s" (which corresponds to disallowed three consecutive digits) and two choices of digit produce an "n". Following an "n" one choice of digit produces an "s" and two choices of digit produce an "n".

The acceptable 5 letter strings, with their counts and a running sum, are \begin{align*} snsns && 3 \cdot 2 \cdot 1 \cdot 2 \cdot 1 = 12 && 12 \\ snsnn && 3 \cdot 2 \cdot 1 \cdot 2 \cdot 2 = 24 && 36 \\ snnsn && 3 \cdot 2 \cdot 2 \cdot 1 \cdot 2 = 24 && 60 \\ snnns && 3 \cdot 2 \cdot 2 \cdot 2 \cdot 1 = 24 && 84 \\ snnnn && 3 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 48 && 132 \\ nsnsn && 6 \cdot 1 \cdot 2 \cdot 1 \cdot 2 = 24 && 156 \\ nsnns && 6 \cdot 1 \cdot 2 \cdot 2 \cdot 1 = 24 && 180 \\ nsnnn && 6 \cdot 1 \cdot 2 \cdot 2 \cdot 2 = 48 && 228 \\ nnsns && 6 \cdot 2 \cdot 1 \cdot 2 \cdot 1 = 24 && 252 \\ nnsnn && 6 \cdot 2 \cdot 1 \cdot 2 \cdot 2 = 48 && 300 \\ nnnsn && 6 \cdot 2 \cdot 2 \cdot 1 \cdot 2 = 48 && 348 \\ nnnns && 6 \cdot 2 \cdot 2 \cdot 2 \cdot 1 = 48 && 396 \\ nnnnn && 6 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 96 && 492 \\ \end{align*} So there are $492$ allowed configurations.

I generally prefer this method because it more directly corresponds to the tree of consecutive digit choices.

Answer 4

Denote by $a_n$ the number of admissible words of length $n\geq1$. Then $a_1=3$, $a_2=9$. Furthermore we have the recursion $$a_n=2a_{n-1}+2a_{n-2}\qquad(n\geq3)\ .\tag{1}$$ Proof. The last two letters of an admissible word $w$ of length $n$ are either different or equal. In the first case the word $w$ results from appending a letter to an admissible word $w'$ of length $n-1$ which is different from the last letter of $w'$. In the second case the word $w$ results from appending two equal letters to an admissible word $w''$ of length $n-2$ which are different from the last letter of $w''$. $\quad\square$

Given the initial conditions one can solve $(1)$ using the "Master Theorem". As only $a_6$ is required we can do the necessary steps by hand and arrive at $a_6=492$.