|
|
A208900
|
|
Number of bitstrings of length n which (if having two or more runs) the last two runs have different lengths.
|
|
5
|
|
|
2, 2, 6, 10, 26, 50, 114, 226, 482, 962, 1986, 3970, 8066, 16130, 32514, 65026, 130562, 261122, 523266, 1046530, 2095106, 4190210, 8384514, 16769026, 33546242, 67092482, 134201346, 268402690, 536838146, 1073676290, 2147418114, 4294836226, 8589803522
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
A run is a maximal subsequence of (possibly just one) identical bits.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 2^n + 2 - 2^(floor(n/2)+1).
a(n) = 3*a(n-1) - 6*a(n-3) + 4*a(n-4), a(0) = 2, a(1) = 2, a(2) = 6, a(3) = 10.
G.f.: x*(2 - 4*x + 4*x^3)/((1-x)*(1-2*x^2)*(1-2*x)).
E.g.f.: - 2*cosh(sqrt(2)*x) + 2*exp(x)*(1 + sinh(x)) - sqrt(2)*sinh(sqrt(2)*x). - Stefano Spezia, Jun 06 2023
|
|
EXAMPLE
|
If n=3 the bitstrings where the last runs have different lengths are 111,000,100,011,110,001 so a(3) = 6.
|
|
MATHEMATICA
|
Table[2 + 2^n - 2^(Floor[n/2] + 1) , {n, 1, 40}]
LinearRecurrence[{3, 0, -6, 4}, {2, 2, 6, 10}, 40]
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|