A364685 The number of binary sequences of length n for which all patterns {0,1},{0,0},{1,0},{1,1} appear for the first time. In particular, three of the patterns will have appeared at least once before the (n-1)st digit in the sequence and the remaining pattern appears for the first and only time at positions {n-1,n} in the sequence.
4, 10, 18, 30, 48, 76, 120, 190, 302, 482, 772, 1240, 1996, 3218, 5194, 8390, 13560, 21924, 35456, 57350, 92774, 150090, 242828, 392880, 635668, 1028506, 1664130, 2692590, 4356672, 7049212, 11405832, 18454990, 29860766, 48315698, 78176404, 126492040, 204668380
Offset: 5
Examples
a(6)=10 is the number of cover time sequences of length 6 for binary patterns of length 2: {{0, 0, 0, 1, 1, 0}, {0, 0, 1, 0, 1, 1}, {0, 0, 1, 1, 1, 0}, {0, 1, 0, 0, 1, 1}, {0, 1, 1, 1, 0, 0}, {1, 0, 0, 0, 1, 1}, {1, 0, 1, 1, 0, 0}, {1, 1, 0, 0, 0, 1}, {1, 1, 0, 1, 0, 0}, {1, 1, 1, 0, 0, 1}}. (Notice that the final two digits in each of these sequences completes the appearance of all four patterns.)
Links
- Evan Fisher, Tianman Huang, and Xiaoshi Wang, Cover Times for Markov Generated Sequences of Length Two, Rocky Mountain J. Math. 50 (3) 957 - 974, June 2020.
- Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).
Programs
-
Mathematica
b[n_]:= b[n] = Tuples[{0, 1}, n]; a1[n_]:= Select[b[n], MatchQ[#, {_, PatternSequence[0, 0], _}] && MatchQ[#, {_, PatternSequence[0, 1], _}] && MatchQ[#, {_, PatternSequence[1, 0], _}] && MatchQ[#, {_, PatternSequence[1, 1], _}] &]; Table[Length[ Select[a1[k], Length[SequencePosition[#, Take[#, -2]]] == 1 &]], {k, 5, 20}]
Formula
a(n) = 2*(n-6+F(n-1)), F(n) is the n-th Fibonacci number A000045(n).
G.f.: 2*x^5*(2*x^2+x-2)/((x^2+x-1)*(x-1)^2).