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

Author

Geoffrey Critzer, Jan 24 2010

Keywords

• nonn
• easy

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.

Examples

			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}}.
		

References

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

Links

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

Programs

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

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 *)

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