Find the number of 7-digit ternary strings that do not have any 0's next to any 1's. 00200211 and 00211200 are 2 strings to be counted, while 00200120 is a string not to be counted.
(A ternary string is a string consisting of only 0's, 1's, and 2's.)
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let x y represent the number of y-digit ternary strings that ends with x . We find these recursive equations: 0 n + 1 = 0 n + 2 n , 1 n + 1 = 1 n + 2 n , 2 n + 1 = 0 n + 1 n + 2 n .
We know that 0 1 = 1 1 = 2 1 = 1 , and we can find the answer: 0 7 + 1 7 + 2 7 = 1 6 9 + 1 6 9 + 1 6 9 = 5 7 7 .