# How many strings of $6$ digits are there which use only the digits $0, 1$, or $2$ and in which $2$, whenever it appears, always does so after $1$?

My attempt at the solution:

Without $$2$$s: $$\Rightarrow 6$$ places, each of which can be filled in two ways.

Hence in total $$2^6$$ ways.

Considering (01) as a set,

0 1 _ _ _ _ $$\Rightarrow$$ Remaining places can be filled in $$3 \cdot 2^3$$ ways (one place with any of the $$3$$ digits and remaining with only $$2$$ digits) . Shifting (01), we have 5 possibilities.

Hence in total $$5 \cdot 3 \cdot 2^3$$ ways

Next possibility, $$\Rightarrow$$ 0 1 0 1 _ _

$$\Rightarrow$$ Remaining places can be filled in $$3 \cdot 2$$ ways (one place with any of the three digits and the remaining with only two digits). Shifting (0101), we have $$6$$ possibilities.

Hence in total $$6 \cdot 3 \cdot 2$$ ways.

Grand Total $$= 32 + 120 + 36 = 188$$.

But the answer given in the book is $$256$$. Help! Thank you in advance.

• Shouldn't you have $\color{green}{12 \_\_\_\_}$ and not $\color{red}{01\_\_\_\_}$ above? Commented Feb 17, 2018 at 10:08
• In the question is the sequence $100002$ a valid sequence? In particular does the digit before $2$ always has to be $1$ or it's enough to have a sinlge $1$ in front of it at any point? Commented Feb 17, 2018 at 10:12
• Oops. Yes it should be 12 _ _ _ _ My bad! @астонвіллаолофмэллбэрг Commented Feb 17, 2018 at 15:35
• @Stefan4024 Its enough to have a single 1 in front of it at any point. Commented Feb 17, 2018 at 15:42

Let $a_n$ be the number of such strings of length $n$ which end in a $0$ or $2$. Also let $b_n$ be the number of such strings of length $n$ which end with $1$. Now obviously we can form the recursion relations:

$$a_{n+1} = a_n + 2b_n$$ $$b_{n+1} = a_n + b_n$$

Here the initial condition is $a_1 = 1, b_1 = 1$. So repeatedly using the relation above it shouldn't be hard to get that $a_2 = 3, b_2 = 2$; $a_3 = 7, b_3 = 5$; $a_4 = 17, b_4 = 12$; $a_5 = 41, b_5 = 29$; $a_6 = 99, b_6 = 70$, so the total number is $169$

Another way is using your method. If there is no $2$ then we have $2^6 = 64$ options. If there's a single two then you can consider $(12)$ as single digit and then place choose it's place in a $5$ digit word and there are $2^4$ options for the remaining $4$ digits. SO the wanted number is $5 \cdot 2^4 = 80$ If there are two twos, then again consider $(12)$ as a single digit. Choose the placement of them in a $4$-digit sequence and the rest two digits can be chosen in $2^2$ ways. So the number of such combinations is $\binom{4}{2} \cdot 2^2 = 24$. If there are three two then we have a single options. Finally the wanted number is:

$$64+80+24+1 = 169$$

[UPDATE]

We can count the number of solutions by the position of the first $2$. If there are no $2$'s then we have $2^6=64$ such sequences. Now obviously we can't have it appear first. If it appears second then the first digit is $1$ and we have $3^4=81$ options for the remaning $4$ digits. In general if the first $2$ appears in the $n$-th position we have:

$$(2^{n-1} - 1)3^{6-n} \text{ sequences}$$

This is true, as we need to exclude the sequence of all zeroes before the $2$. Summing all such possibilities we get:

$$64+81+81+63+45+31 = 365$$

Note that this result is expected as there are exactly $3^6 = 729$ such sequences and the $1$ will appear before $2$ in exactly half of them, because of the symmetry. And indeed $\frac{729}{2} = 364.5$. Note that we are off by one as the sequence of all zeroes doesn't count in any set of sequences.

• But OP says that the answer in the book is 256 Commented Feb 17, 2018 at 11:13
• @Manthanein Then either the book answer is wrong or I have misunderstood the problem. Commented Feb 17, 2018 at 11:14
• Can you please elaborate how you got that recurrence relation. I did not get it properly Commented Feb 17, 2018 at 11:19
• @Manthanein To get the number of sequences ending in $2$ we have to take a sequence with lenght less by one and ending in $1$, which is where $b_n$ comes from in the first equation. Similarly for $0$ we don't have any constrain, so we can take any sequence of length less by one and adjoin $0$ at the end. Hence $a_{n+1} = a_n + 2b_n$. Similarly for $b_{n+1}$ ,as we can get a sequence of length $n+1$ ending in $1$ by adding $1$ to the end of any sequence of lenght $n$. Commented Feb 17, 2018 at 11:21
• Just checked! Seems perfect! I can understand. So the answer is 169 if digit before 2 is always 1 and is 365 if 1 can appear wherever before 2. Thank you. Commented Feb 17, 2018 at 17:06

First place can only be filled by 1 - So forget it.

For Last 4 places you can fill with 12, 0, 1 with repeating numbers so 43 = 64

Second place can be occupied by 0,1,2 = 64 * 3 = 192

So total ways = 64 + 192 = 256.