A172060 The number of returns to the origin in all possible one-dimensional walks of length 2n.

0, 2, 14, 76, 374, 1748, 7916, 35096, 153254, 661636, 2831300, 12030632, 50826684, 213707336, 894945944, 3734901296, 15540685574, 64496348516, 267060529364, 1103587381256, 4552196053844, 18747042089816, 77092267322984, 316602500019536, 1298657603761244

Offset

0,2

Comments

a(n)/4^n is the expected number of times a gambler will return to his break-even point while making 2n equal wagers on the outcome of a fair coin toss. Note the surprisingly low and slow growth of this expectation.

References

W. Feller, An Introduction to Probability Theory and its Applications, Vol 1, 3rd ed. New York: Wiley, pp. 67-97, 1968.

Links

Table of n, a(n) for n=0..24.

M. Bona, Non-overlapping permutation patterns, PU. M. A. Vol. 22 (2012), 99-105. - N. J. A. Sloane, Oct 13 2012

Formula

a(n) = (2n+1)!/(n!)^2 - 4^n.

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

O.g.f.: (1-(1-4x)^(1/2))/(1-4x)^(3/2).

a(n) = A002457(n) - A000302(n). - Wesley Ivan Hurt, Mar 24 2015

a(n) = 2*A000531(n). - R. J. Mathar, Jan 03 2018

Example

a(2) = 14 because there are fourteen 0's in the set of all possible walks of length 4: {{-1, -2, -3, -4}, {-1, -2, -3, -2}, {-1, -2, -1, -2}, {-1, -2, -1, 0}, {-1, 0, -1, -2}, {-1, 0, -1, 0}, {-1, 0, 1, 0}, {-1, 0, 1, 2}, {1, 0, -1, -2}, {1, 0, -1, 0}, {1, 0, 1, 0}, {1, 0, 1, 2}, {1, 2, 1, 0}, {1, 2, 1, 2}, {1, 2, 3, 2}, {1, 2, 3, 4}}.

Maple

A172060:=n->(2*n+1)!/(n!)^2 - 4^n: seq(A172060(n), n=0..30); # Wesley Ivan Hurt, Mar 24 2015

Mathematica

Table[Count[Flatten[Map[Accumulate, Strings[{-1, 1}, n]]], 0], {n, 0, 20, 2}]
CoefficientList[Series[(1 - (1 - 4 x)^(1/2)) / (1 - 4 x)^(3/2), {x, 0, 33}], x] (* Vincenzo Librandi, Mar 25 2015 *)

Prog

(Magma) [Factorial(2*n+1)/Factorial(n)^2 - 4^n : n in [0..30]]; // Wesley Ivan Hurt, Mar 24 2015
(Magma) [0] cat [n le 1 select 2 else 4*Self(n-1)+ Binomial(2*n, n): n in [1..30]]; // Vincenzo Librandi, Mar 25 2015

Crossrefs

Sequence in context: A304049 A197874 A104871 * A277297 A185055 A034573

Adjacent sequences: A172057 A172058 A172059 * A172061 A172062 A172063

Keyword

nonn,easy

Author

Geoffrey Critzer, Jan 24 2010

Status

approved