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

Author

Geoffrey Critzer, Jan 12 2013

Keywords

• nonn

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) + ...

Examples

			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.
		

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

Crossrefs

Cf. A119706.

Programs

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}]]

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).