A230137 a(n)/2^n is the expected value of the maximum of the number of heads and the number of tails when n fair coins are tossed.

0, 2, 6, 18, 44, 110, 252, 588, 1304, 2934, 6380, 14036, 30120, 65260, 138712, 297240, 627248, 1332902, 2796876, 5904516, 12333320, 25899972, 53897096, 112693928, 233776464, 487034300, 1007623032, 2092755528, 4319728784, 8948009624, 18432890160, 38094639664

Offset: 0

Author

Geoffrey Critzer, Oct 10 2013

Keywords

• nonn

Examples

			a(2) = 6 because there are four possible events when 2 coins are tossed: HH, HT, TH, TT.  The maximum of the number of heads and number of tails is respectively: 2 + 1 + 1 + 2 = 6.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Georg Braun, On the Growth of a Ballistic Deposition Model on Finite Graphs, arXiv:2001.09836 [math.PR], 2020.
• D. R. L. Brown, Bounds on surmising remixed keys, IACR, Report 2015/375, 2015-2016. See Table 1.

Programs

Maple

a:= proc(n) option remember; `if`(n<3, n*(1+n),
       2*n/(n-1)*a(n-1) +4*(n-3)/(n-2)*a(n-2) -8*a(n-3))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Oct 10 2013

Mathematica

nn=15;even=Table[n 2^(2n)+n Binomial[2n,n],{n,0,nn}];odd=Table[2Sum[ Binomial[2n+1,k]k,{k,n+1,2n+1}],{n,0,nn}];Riffle[even,odd]

Formula

a(2n) = 2*Sum_{k=n+1..2n} binomial(2n,k)*k + binomial(2n,n)*n.

a(2n+1) = 2*Sum_{k=n+1..2n+1} binomial(2n+1,k)*k.

a(n) = 2*n/(n-1)*a(n-1) +4*(n-3)/(n-2)*a(n-2) -8*a(n-3) for n>2, else a(n) = n*(1+n). - Alois P. Heinz, Oct 10 2013

From Vaclav Kotesovec, Jul 20 2019: (Start)

a(2*n) = (4^n + binomial(2*n,n))*n.

a(2*n+1) = (4^n + binomial(2*n,n))*(2*n+1). (End)