login
A119706
Total length of longest runs of 1's in all bitstrings of length n.
7
1, 4, 11, 27, 62, 138, 300, 643, 1363, 2866, 5988, 12448, 25770, 53168, 109381, 224481, 459742, 939872, 1918418, 3910398, 7961064, 16190194, 32893738, 66772387, 135437649, 274518868, 556061298, 1125679616, 2277559414, 4605810806, 9309804278, 18809961926
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
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)
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
# second Maple program:
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
Cf. A334833.
Sequence in context: A035593 A295056 A160399 * A034345 A036890 A000253
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