How many length-5 ternary strings are there without 4 consecutive 0s, 1s or 2s? For example, 20000 and 11112 are excluded.

1.3k Views Asked by At

My answer is 237 and my approach is not vary smart. would like to know if they are more wise method for it. Here is my thinking: $3^5= 243. $ Then minus 15, since

(1) 0 0 0 0 or 0 0 0 0 (1),  
(2) 0 0 0 0 or 0 0 0 0 (2),  0 0 0 0 0,      
(0) 1 1 1 1 or 1 1 1 1 (0),  
(2) 1 1 1 1 or 1 1 1 1 (2),  1 1 1 1 1,  
(0) 2 2 2 2 or 2 2 2 2 (0),
(1) 2 2 2 2 or 2 2 2 2 (1),
(0) 2 2 2 2 or 2 2 2 2 (0),  2 2 2 2 2,  

Wondering if there is any formula to calculate more systematically?

2

There are 2 best solutions below

1
On

I don't think you will get more systematic, except that you might do that counting in fewer steps by saying in pseudocode logic if $(x \neq A)$ $\{xAAAA~\text{or}~AAAAx\}~\text{else}~\{xAAAA\}$ where $x,A \in \{0,1,2\}$ implies a count of $2 \cdot 3 \cdot 2 + 1 \cdot 3 \cdot 1 = 15$.

The advantage here is we can compute the number if our digits are a higher base. As is, it isn't definitively simpler.

0
On

Let us count the number of strings where one symbol, call it $a$ appears as $aaaa$ in the string. You have $5$ places to fill to make a complete string, out of which $4$ (consecutive positions) will be occupied by the repeated symbol ($a$). So your string will be of the form $Xaaaa$ or $aaaaX$. In each scenario, the blank space can be filled in three ways by either $a$ or $b$ or $c$. So in all $6$ possibilities. However, when $a$ is filled in the blank space, then we get the same string $\color{red}{a}aaaa=aaaa\color{red}{a}$ and we have counted it twice. So in all $5$ strings, will be there where a given symbol has appeared in $4$ consecutive positions. Now for each symbol you can do this, so in all $15$ strings with this property.

General problem: If you are given $n$ symbols to make strings of length $L$ such that one symbol appears in $L-1$ consecutive positions. Then the number of such strings are given by $n(2n-1)$.