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.
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).
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
KEYWORD
nonn,easy
AUTHOR
Evan Fisher and Ruiqi (Violet) Cai, Aug 02 2023
STATUS
approved