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

%I #25 Jan 21 2023 02:18:20

%S 0,1,4,11,25,52,103,199,380,724,1382,2649,5103,9881,19224,37559,73646,

%T 144848,285623,564429,1117396,2215436,4398054,8740266,17385207,

%U 34607218,68934319,137386725,273942683,546450648,1090419638

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

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

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

%H G. C. Greubel, <a href="/A209232/b209232.txt">Table of n, a(n) for n = 0..1000</a>

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

%e 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.

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

%Y Cf. A119706.

%K nonn

%O 0,3

%A _Geoffrey Critzer_, Jan 12 2013