login
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.
0
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,1
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.
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).
EXAMPLE
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.)
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}]
CROSSREFS
Sequence in context: A332490 A008246 A301284 * A024983 A009896 A027372
KEYWORD
nonn,easy
AUTHOR
Evan Fisher and Ruiqi (Violet) Cai, Aug 02 2023
STATUS
approved