A209232 a(n) is 2^n times the expected value of the shortest run of 0's in a binary word of length n.

0, 1, 4, 11, 25, 52, 103, 199, 380, 724, 1382, 2649, 5103, 9881, 19224, 37559, 73646, 144848, 285623, 564429, 1117396, 2215436, 4398054, 8740266, 17385207, 34607218, 68934319, 137386725, 273942683, 546450648, 1090419638

Offset

0,3

Comments

a(n) is also the sum of the number of binary words containing at least one 0 and having every consecutive run of 0's of length >= i for i >= 1. In other words, a(n) = A000225(n) + A077855(n) + A130578(n) + A209231(n) + ...

References

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, Chapter 7.

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Formula

O.g.f.: Sum_{k >= 1} (x^k/(1 - x) + 1) / ((1 - x^(k + 1)/(1 - x)^2)) * 1/(1 - x) - 1/(1 - x).

Example

a(3) = 11. To the length 3 binary words {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1}, {1, 0, 0}, {1, 0, 1}, {1, 1, 0}, {1, 1, 1} we have respectively shortest zero runs of length 3 + 2 + 1 + 1 + 2 + 1 + 1 + 0 = 11.

Mathematica

nn = 30; Apply[Plus, Table[a = x^n/(1 - x); CoefficientList[Series[(a + 1)/((1 - a x/(1 - x)))*1/(1 - x) - 1/(1 - x), {x, 0, nn}], x], {n, 1, nn}]]

Crossrefs

Cf. A119706.

Sequence in context: A356619 A014173 A290986 * A266337 A262158 A156127

Adjacent sequences: A209229 A209230 A209231 * A209233 A209234 A209235

Keyword

nonn

Author

Geoffrey Critzer, Jan 12 2013

Status

approved