cp's OEIS Frontend

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

%I A119706 #52 Jun 05 2025 10:13:35
%S A119706 1,4,11,27,62,138,300,643,1363,2866,5988,12448,25770,53168,109381,
%T A119706 224481,459742,939872,1918418,3910398,7961064,16190194,32893738,
%U A119706 66772387,135437649,274518868,556061298,1125679616,2277559414,4605810806,9309804278,18809961926
%N A119706 Total length of longest runs of 1's in all bitstrings of length n.
%C A119706 a(n) divided by 2^n is the expected value of the longest run of heads in n tosses of a fair coin.
%C A119706 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
%D A119706 A. M. Odlyzko, Asymptotic Enumeration Methods, pp. 136-137
%D A119706 R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, page 372.
%H A119706 Alois P. Heinz, <a href="/A119706/b119706.txt">Table of n, a(n) for n = 1..1000</a>
%H A119706 Steven Finch, <a href="https://arxiv.org/abs/2003.09458">Cantor-solus and Cantor-multus distributions</a>, arXiv:2003.09458 [math.CO], 2020.
%F A119706 a(n+1) = 2*a(n) + A007059(n+2)
%F A119706 a(n) > 2*a(n-1). a(n) = Sum_{i=1..(2^n)-1} A038374(i). - _R. J. Mathar_, Jun 15 2006
%F A119706 From _Geoffrey Critzer_, Jan 12 2013: (Start)
%F A119706 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
%F A119706 a(n) = Sum_{k=1..n} A048004(n,k) * k.
%F A119706 (End)
%F A119706 Conjecture: a(n) = A102712(n+1)-2^n. - _R. J. Mathar_, Jun 05 2025
%e A119706 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.
%p A119706 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
%p A119706 # second Maple program:
%p A119706 b:= proc(n, m) option remember; `if`(n=0, 1,
%p A119706       `if`(m=0, add(b(n-j, j), j=1..n),
%p A119706       add(b(n-j, min(n-j, m)), j=1..min(n, m))))
%p A119706     end:
%p A119706 a:= proc(n) option remember;
%p A119706      `if`(n<2, n, 2*a(n-1) +b(n, 0))
%p A119706     end:
%p A119706 seq(a(n), n=1..40);  # _Alois P. Heinz_, Dec 19 2014
%t A119706 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 *)
%Y A119706 Cf. A334833.
%K A119706 nonn
%O A119706 1,2
%A A119706 _Adam Kertesz_, Jun 09 2006, Jun 13 2006
%E A119706 More terms from _R. J. Mathar_, Jun 15 2006
%E A119706 Name edited by _Alois P. Heinz_, Mar 18 2020