

A307768


Number of nstep random walks on a line starting from the origin and returning to it at least once.


2



0, 0, 2, 4, 10, 20, 44, 88, 186, 372, 772, 1544, 3172, 6344, 12952, 25904, 52666, 105332, 213524, 427048, 863820, 1727640, 3488872, 6977744, 14073060, 28146120, 56708264, 113416528, 228318856, 456637712, 918624304, 1837248608, 3693886906, 7387773812, 14846262964, 29692525928
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

a(n)/2^n tends to 1 as n goes to infinity; this means that on the line any random walk returns sooner or later to its starting point with a probability 1.
a(n) is also the number of headsortails games of length n during which at some point there are as many heads as tails.


LINKS

Robert Israel, Table of n, a(n) for n = 0..3318


FORMULA

a(n) = 2^n  A063886(n).
a(n+1) = 2*A045621(n) = 2*(2^n  binomial(n,floor(n/2))).
a(2n) = 2^(2n)  binomial(2n,n); a(2n+1) = 2*a(2n).
G.f.: (1sqrt(14*x^2))/(12*x).  Alois P. Heinz, May 05 2019
n*(a(n)2*a(n1))  4*(n3)*(a(n2)2*a(n3)) = 0.  Robert Israel, May 06 2019
a(2n+2)  2*a(2n+1) = A284016(n) = 2*Catalan(n).  Robert FERREOL, Aug 26 2019


EXAMPLE

The a(3)=4 threestep walks returning to 0 are [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1], [0, 1, 0, 1].
The a(4)=10 threestep walks returning to 0 are [0, 1, 2, 1, 0], [0, 1, 0, 1, 2], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [0, 1, 0, 1, 2], [0, 1, 0, 1, 2], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [0, 1, 0, 1, 2], [0, 1, 2, 1, 0].


MAPLE

b:=n>piecewise(n mod 2 = 0, binomial(n, n/2), 2*binomial(n1, (n1)/2)):
seq(2^nb(n), n=0..20);


MATHEMATICA

a[n_] := If[n == 0, 0, 2^n  2*Binomial[n1, Floor[(n1)/2]]];
Array[a, 36, 0] (* JeanFrançois Alcover, May 05 2019 *)


CROSSREFS

Cf. A063886, A045621.
Sequence in context: A121880 A094536 A323445 * A297183 A232466 A003407
Adjacent sequences: A307765 A307766 A307767 * A307769 A307770 A307771


KEYWORD

nonn,walk


AUTHOR

Robert FERREOL, Apr 27 2019


STATUS

approved



