|
|
A307768
|
|
Number of n-step 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 heads-or-tails games of length n during which at some point there are as many heads as tails.
|
|
LINKS
|
|
|
FORMULA
|
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).
n*(a(n)-2*a(n-1)) - 4*(n-3)*(a(n-2)-2*a(n-3)) = 0. - Robert Israel, May 06 2019
|
|
EXAMPLE
|
The a(3)=4 three-step 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 three-step 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(n-1, (n-1)/2)):
seq(2^n-b(n), n=0..20);
|
|
MATHEMATICA
|
a[n_] := If[n == 0, 0, 2^n - 2*Binomial[n-1, Floor[(n-1)/2]]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,walk
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|