How many 19 digit strings of X's & O's are there that begin with and end with an O,& contain no two O's consecutive or three consecutive X's?

Question

How many 19 digit strings of X's & O's are there that begin with and end with an O,& contain no two O's consecutive or three consecutive X's

Answer 1

Start with one end



O



the next string to be added must be either



XO or XXO. There are no other choices



the next string after that must be XO or XXO, too, and so on an so forth.



if you had 6 strings of all XXO added on, you'd have one valid combination, because that would end in O, and add on a total of 18 digits, making a 19-digit string.



So the question is, how many ways can you add together



(2 or 3) + (2 or 3) + ... + (2 or 3) = 18?



Any 3's must be in pairs, or else the total number of digits would not be even and make 18. So there must be no 3's, or 2 3's, or 4 3's, or 6 3's. Each of these cases dictates the number of 2's



a) 0 3's and 9 2's

b) 2 3's and 6 2's

c) 4 3's and 3 2's

d) 6 3's and 0 2's



How many ways can we arrange each of these cases? Cases a) and d) are obviously 1 each.



Case b) is (the number of ways to arrange 8 objects) / ((the number of ways to arrange 2 objects)(the number of ways to arrange 6 objects) = 8!/(2!6!) = 28. Or, if you will C(8,2) or C(8.6). Think of 8 generic strings, and you want to select 2 of them to be length 3.



case c) is therefore C(7,4) = 35



Add up all the cases and you're done.

Answer 2

We derive a formula for the number of n digit-long strings of the given type: For any integer n ≥ 2



• let O_(n) be the set of n digit {O, X}-strings beginning with O and not containing substrings OO, XXX

• let O_OX(n) be the subset of O_(n) whose elements end with OX,

• let O_XO(n) be the subset of O_(n) whose elements end with XO,

• let O_XX(n) be the subset of O_(n) whose elements end with XX.



For example [1]:



O_OX(2) = {OX}, . . . . . . . . . . . . . . . . O_XO(2) = {}, . . . . . . . . . . . . . . . . . . .O_XX(2) = {},

O_OX(3) = {}, . . . . . . . . . . . . . . . . . . .O_XO(3) = {OXO}, . . . . . . . . . . . . . . .O_XX(3) = {OXX},

O_OX(4) = {OXOX}, . . . . . . . . . . . . . O_XO(4) = {OXXO}, . . . . . . . . . . . . . .O_XX(4) = {},

O_OX(5) = {OXXOX}, . . . . . . . . . . . . O_XO(5) = {OXOXO}, . . . . . . . . . . . . O_XX(5) = {OXOXX},

O_OX(6) = {OXOXOX}, . . . . . . . . . . .O_XO(6) = {OXXOXO,OXOXXO}, . . . O_XX(6) = {OXXOXX},

O_OX(7) = {OXXOXOX,OXOXXOX}, O_XO(7) = {OXOXOXO,OXXOXXO}, O_XX(7) = {OXOXOXX},



·

.

:

Since O_OX(n), O_XO(n), O_XX(n) are pairwise disjoint and together have union O_(n), we have



|O_(n)| = |O_OX(n)| + |O_XO(n)| + |O_XX(n)|,



where |•| denotes set cardinality. Moreover note for all n ≥ 3 that



• appending an X puts O_XO(n–1) in a 1-to-1 correspondence to O_OX(n),

• appending an O puts O_OX(n–1) ∪ O_XX(n–1) in a 1-to-1 correspondence to O_XO(n),

• appending an X puts O_OX(n–1) in a 1-to-1 correspondence to O_XX(n).



Thus



[2]: |O_OX(n)| = |O_XO(n–1)|,

[3]: |O_XO(n)| = |O_OX(n–1)| + |O_XX(n–1)|,

[4]: |O_XX(n)| = |O_OX(n–1)|.



This lets us obtain a 3rd order linear recursion on A(n) := |O_XO(n)|:



|O_XO(n)|

= |O_OX(n–1)| + |O_XX(n–1)| . . . . . . via [3]

= |O_XO(n–2)| + |O_OX(n–2)| . . . . . . via [2] and [4]

= |O_XO(n–2)| + |O_XO(n–3)| . . . . . . via [2].



So



[5]: A(n) = A(n–2) + A(n–3).



We already know from example [1] above that (A(2), ... , A(7)) = (0, 1, 1, 1, 2 ,2), corroborating [5]. With a few more applications of [5] we get



(A(2), ... , A(19)) = (0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65).



So the answer is 65.

Answer 3

??????????????????