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,2

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.

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)

Example

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.

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]

Crossrefs

Sequence in context: A233531 A320303 A319415 * A120414 A251685 A341490

Adjacent sequences: A230134 A230135 A230136 * A230138 A230139 A230140

Keyword

nonn

Author

Geoffrey Critzer, Oct 10 2013

Status

approved