|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
5,1
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
