OFFSET
1,2
COMMENTS
a(n) divided by 2^n is the expected value of the longest run of heads in n tosses of a fair coin.
a(n) is also the sum of the number of binary words with at least one run of consecutive 0's of length >= i for i>=1. In other words A000225 + A008466 + A050231 + A050232 + ... . - Geoffrey Critzer, Jan 12 2013
REFERENCES
A. M. Odlyzko, Asymptotic Enumeration Methods, pp. 136-137
R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 372.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..1000
Félix Balado and Guénolé C. M. Silvestre, Systematic Enumeration of Fundamental Quantities Involving Runs in Binary Strings, arXiv:2602.10005 [math.CO], 2026. See p. 30.
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
FORMULA
a(n+1) = 2*a(n) + A007059(n+2)
a(n) > 2*a(n-1). a(n) = Sum_{i=1..2^n-1} A038374(i). - R. J. Mathar, Jun 15 2006
From Geoffrey Critzer, Jan 12 2013: (Start)
O.g.f.: Sum_{k>=1} 1/(1-2*x) - (1-x^k)/(1-2*x+x^(k+1)). - Corrected by Steven Finch, May 16 2020
a(n) = Sum_{k=1..n} A048004(n,k) * k. (End)
Conjecture: a(n) = A102712(n+1)-2^n. - R. J. Mathar, Jun 05 2025
O.g.f.: Sum_{k>=1} k * x^k * (1-x)^2 / ((1-2*x+x^(k+1)) * (1-2*x+x^(k+2))). - Félix Balado, Oct 20 2025
EXAMPLE
a(3)=11 because for the 8(2^3) possible runs 0 is longest run of heads once, 1 four times, 2 two times and 3 once and 0*1+1*4+2*2+3*1 = 11.
MAPLE
A038374 := proc(n) local nshft, thisr, resul; nshft := n ; resul :=0 ; thisr :=0 ; while nshft > 0 do if nshft mod 2 <> 0 then thisr := thisr+1 ; else resul := max(resul, thisr) ; thisr := 0 ; fi ; nshft := floor(nshft/2) ; od ; resul := max(resul, thisr) ; RETURN(resul) ; end : A119706 := proc(n) local count, c, rlen ; count := array(0..n) ; for c from 0 to n do count[c] := 0 ; od ; for c from 0 to 2^n-1 do rlen := A038374(c) ; count[rlen] := count[rlen]+1 ; od ; RETURN( sum('count[c]*c', 'c'=0..n) ); end: for n from 1 to 40 do print(n, A119706(n)) ; od : # R. J. Mathar, Jun 15 2006
# Alternative:
b:= proc(n, m) option remember; `if`(n=0, 1,
`if`(m=0, add(b(n-j, j), j=1..n),
add(b(n-j, min(n-j, m)), j=1..min(n, m))))
end:
a:= proc(n) option remember;
`if`(n<2, n, 2*a(n-1) +b(n, 0))
end:
seq(a(n), n=1..40); # Alois P. Heinz, Dec 19 2014
MATHEMATICA
nn=10; Drop[Apply[Plus, Table[CoefficientList[Series[1/(1-2x)-(1-x^n)/(1-2x+x^(n+1)), {x, 0, nn}], x], {n, 1, nn}]], 1] (* Geoffrey Critzer, Jan 12 2013 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Adam Kertesz, Jun 09 2006, Jun 13 2006
EXTENSIONS
More terms from R. J. Mathar, Jun 15 2006
Name edited by Alois P. Heinz, Mar 18 2020
STATUS
approved