A119706 Total length of longest runs of 1's in all bitstrings of length n.

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

Author

Adam Kertesz, Jun 09 2006, Jun 13 2006

Keywords

• nonn

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

Examples

			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.
		

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
• Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.

Crossrefs

Cf. A334833.

Programs

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

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

Extensions

More terms from R. J. Mathar, Jun 15 2006

Name edited by Alois P. Heinz, Mar 18 2020