login
A172060
The number of returns to the origin in all possible one-dimensional walks of length 2n.
2
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
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
KEYWORD
nonn,easy
AUTHOR
Geoffrey Critzer, Jan 24 2010
STATUS
approved