

A208901


Number of bitstrings of length n (with at least two runs) where the last two runs have different lengths.


5



0, 0, 4, 8, 24, 48, 112, 224, 480, 960, 1984, 3968, 8064, 16128, 32512, 65024, 130560, 261120, 523264, 1046528, 2095104, 4190208, 8384512, 16769024, 33546240, 67092480, 134201344, 268402688, 536838144, 1073676288, 2147418112, 4294836224, 8589803520
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

A run is a maximal subsequence of (possibly just one) identical bits.


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Aruna Gabhe, Problem 11623, Am. Math. Monthly 119 (2012) 161.
Index entries for linear recurrences with constant coefficients, signature (2,2,4).


FORMULA

a(n) = 2^n  2^(floor(n/2)+1).
a(n) = 2*a(n1) + 2*a(n2)  4*a(n3), a(0) = 0, a(1) = 0, a(2) = 4.
G.f.: 4*x^2/(1  2*x  2*x^2 + 4*x^3).


EXAMPLE

If n=3 the bitstrings (with at least two runs) where the last runs have different lengths are 100,011,110,001 so a(3) = 4.


MATHEMATICA

Table[2^n  2^(Floor[ n/2] + 1) , {n, 1, 40}]
LinearRecurrence[{2, 2, 4}, {0, 0, 4}, 40]


CROSSREFS

Cf. A056453, A208900, A208902, A208903.
Sequence in context: A180002 A266821 A306484 * A319721 A115641 A153334
Adjacent sequences: A208898 A208899 A208900 * A208902 A208903 A208904


KEYWORD

nonn,easy


AUTHOR

David Nacin, Mar 03 2012


STATUS

approved



