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