%I #64 Sep 08 2022 08:44:56
%S 0,1,2,5,10,22,44,93,186,386,772,1586,3172,6476,12952,26333,52666,
%T 106762,213524,431910,863820,1744436,3488872,7036530,14073060,
%U 28354132,56708264,114159428,228318856,459312152,918624304,1846943453,3693886906
%N a(n) = 2^n - binomial(n, floor(n/2)).
%C p(n) = a(n)/2^n is the probability that a majority of heads had occurred at some point after n flips of a fair coin. For example, after 3 flips of a coin, the probability is 5/8 that a majority of heads had occurred at some point. (First flip is heads, p=1/2, or sequence THH, p=1/8.) - _Brian Galebach_, May 14 2001
%C Hankel transform is (-1)^n*n. - _Paul Barry_, Jan 11 2007
%C Hankel transform of a(n+1) is A127630. - _Paul Barry_, Sep 01 2009
%C a(n) is the number of n-step walks on the number line that are positive at some point along the walk. - _Benjamin Phillabaum_, Mar 06 2011
%H Vincenzo Librandi, <a href="/A045621/b045621.txt">Table of n, a(n) for n = 0..247</a>
%H Kairi Kangro, Mozhgan Pourmoradnasseri, Dirk Oliver Theis, <a href="http://arxiv.org/abs/1603.01422">Short note on the number of 1-ascents in dispersed dyck paths</a>, arXiv:1603.01422 [math.CO], 2016.
%H S. Mason and J. Parsley, <a href="http://arxiv.org/abs/1109.1082">A geometric and combinatorial view of weighted voting</a>, arXiv preprint arXiv:1109.1082 [math.CO], 2011.
%F a(n) = 2^n - A001405(n).
%F a(2*k) = 2*a(2*k-1), a(2*k+1) = 2*a(2*k) + Catalan(k).
%F a(n+1) = b(0)*b(n)+b(1)*b(n-1)+...+b(n)*b(0), b(k)=C(k, [ k/2 ]).
%F G.f.: c(x^2)*x/(1-2*x) where c(x) = g.f. for Catalan numbers A000108.
%F a(n) = A054336(n, 1) (second column of triangle).
%F E.g.f.: exp(2*x) - I_0(2*x) - I_1(2*x) where I_n(x) is n-th modified Bessel function as a function of x. - _Benjamin Phillabaum_, Mar 06 2011
%F a(2*n+1) = A000346(n); a(2*n) = A068551(n). - _Emeric Deutsch_, Nov 16 2003
%F a(n) = Sum_{k=0..n-1} binomial(n, floor(k/2)). - _Paul Barry_, Aug 05 2004
%F a(n+1) = 2*a(n) + Catalan(n/2)*(1+(-1)^n)/2. - _Paul Barry_, Aug 05 2004
%F a(n+1) = Sum_{k=0..floor(n/2)} 2^(n-2*k)*A000108(k). - _Paul Barry_, Sep 01 2009
%F (n+1)*a(n) +2*(-n-1)*a(n-1) +4*(-n+2)*a(n-2) +8*(n-2)*a(n-3) = 0. - _R. J. Mathar_, Dec 02 2012
%p seq( 2^n -binomial(n,floor(n/2)), n=0..35); # _G. C. Greubel_, Jan 13 2020
%t Table[2^n - Binomial[n, Floor[n/2]], {n, 0, 35}] (* _Roger L. Bagula_, Aug 26 2006 *)
%o (PARI) {a(n)=if(n<0, 0, 2^n -binomial(n, n\2))} /* _Michael Somos_, Oct 31 2006 */
%o (Magma) [2^n - Binomial(n, Floor(n/2)): n in [0..35]]; // _Bruno Berselli_, Mar 08 2011
%o (Sage) [2^n -binomial(n,floor(n/2)) for n in (0..35)] # _G. C. Greubel_, Jan 13 2020
%o (GAP) List([0..35], n-> 2^n - Binomial(n, Int(n/2)) ); # _G. C. Greubel_, Jan 13 2020
%Y Cf. A000108, A001405, A000346, A054336, A068551.
%K nonn
%O 0,3
%A David M Bloom, Brooklyn College
%E Edited by _N. J. A. Sloane_, Oct 08 2006
%E Adjustments to formulas (correcting offsets) from _Michael Somos_, Oct 31 2006