|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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).
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|