|
%I #23 Sep 08 2022 08:45:50
%S 0,2,14,76,374,1748,7916,35096,153254,661636,2831300,12030632,
%T 50826684,213707336,894945944,3734901296,15540685574,64496348516,
%U 267060529364,1103587381256,4552196053844,18747042089816,77092267322984,316602500019536,1298657603761244
%N The number of returns to the origin in all possible one-dimensional walks of length 2n.
%C 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.
%D W. Feller, An Introduction to Probability Theory and its Applications, Vol 1, 3rd ed. New York: Wiley, pp. 67-97, 1968.
%H M. Bona, <a href="http://www.mat.unisi.it/newsito/puma/public_html/22_2/bona.pdf">Non-overlapping permutation patterns</a>, PU. M. A. Vol. 22 (2012), 99-105. - _N. J. A. Sloane_, Oct 13 2012
%F a(n) = (2n+1)!/(n!)^2 - 4^n.
%F a(n) = 4*a(n-1) + binomial(2n,n).
%F O.g.f.: (1-(1-4x)^(1/2))/(1-4x)^(3/2).
%F a(n) = A002457(n) - A000302(n). - _Wesley Ivan Hurt_, Mar 24 2015
%F a(n) = 2*A000531(n). - _R. J. Mathar_, Jan 03 2018
%e 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}}.
%p A172060:=n->(2*n+1)!/(n!)^2 - 4^n: seq(A172060(n), n=0..30); # _Wesley Ivan Hurt_, Mar 24 2015
%t Table[Count[Flatten[Map[Accumulate, Strings[{-1, 1}, n]]], 0], {n, 0, 20, 2}]
%t CoefficientList[Series[(1 - (1 - 4 x)^(1/2)) / (1 - 4 x)^(3/2), {x, 0, 33}], x] (* _Vincenzo Librandi_, Mar 25 2015 *)
%o (Magma) [Factorial(2*n+1)/Factorial(n)^2 - 4^n : n in [0..30]]; // _Wesley Ivan Hurt_, Mar 24 2015
%o (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
%K nonn,easy
%O 0,2
%A _Geoffrey Critzer_, Jan 24 2010
|
