How many strings of $6$ digits, in which the digit $2,$ whenever it appear, at always does so after $1$, is

220 Views Asked by At

How many strings of $6$ digits are there which use only the digits $0,1$ and $2$ and in which the digit $2,$ whenever it appear, at always does so after $1$, is

Plan

Total number of $6$ digits number is

$2\cdot 3\cdot 3 \cdot 3 \cdot 3 \cdot 3=2\cdot 3^5=243\cdot 2 = 486$

Edited

If $6$ digit string start with $1$. Then ways is $3^5$

If $6$ digit string start with $12$. Then ways is $3^4$

did not know how can i find cases, help me please

1

There are 1 best solutions below

2
On

Taking lulu's suggestion in comments: Every string of length $n$ that satisfies the constraints must end in $0$, $1$, or $12$, and deleting any of these suffixes from the string must give a valid (possibly empty) string of length $n-1$ (in the first two cases) or $n-2$ (in the last). Thus, denoting the number of valid strings of length by $F(n)$, we have the linear recurrence $$F(n) = 2F(n-1) + F(n-2)$$ with initial conditions $F(0) = 1$ (the empty string) and $F(1) = 2$. The first few values of $F$ may be easily tabulated:

\begin{array}{c|c} n & F(n) \\ \hline 0 & 1\\ 1 & 2 \\ 2 & 5\\ 3 & 12\\ 4 & 29 \\ 5 & 70 \\ 6 & 169 \\ \end{array}

Standard linear recurrence techniques give a general solution $$F(n) = \left( \frac{1}{2} + \frac{\sqrt{2}}{4} \right) \left( 1 + \sqrt{2}\right)^n + \left( \frac{1}{2} - \frac{\sqrt{2}}{4} \right) \left( 1 - \sqrt{2}\right)^n.$$

To establish the plausibility of this method, one may enumerate by hand the strings of length $3$: there are $8$ containing only the digits $0$ and $1$ as well as $4$ containing a $2$, namely $\{012, 112, 120, 121\}$.