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
Robert Israel, Table of n, a(n) for n = 0..3318
Monique Laurent, Sven Polak, and Luis Felipe Vargas, Semidefinite approximations for bicliques and biindependent pairs, arXiv:2302.08886 [math.CO], 2023.
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.: (1-sqrt(1-4*x^2))/(1-2*x). - Alois P. Heinz, May 05 2019
n*(a(n)-2*a(n-1)) - 4*(n-3)*(a(n-2)-2*a(n-3)) = 0. - Robert Israel, May 06 2019
a(2n+2) - 2*a(2n+1) = A284016(n) = 2*Catalan(n). - Robert FERREOL, Aug 26 2019
From Mélika Tebni, Jun 19 2024: (Start)
E.g.f.: exp(2*x) - Integral_{x=-oo..oo} (1/x + 2)*BesselI(1, 2*x) dx - BesselI(1, 2*x).
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);
# second program:
A307768 := series(exp(2*x) - int((1/x + 2)*BesselI(1, 2*x), x) - BesselI(1, 2*x), x = 0, 36): seq(n!*coeff(A307768, x, n), n = 0 .. 35); # Mélika Tebni, Jun 19 2024
MATHEMATICA
a[n_] := If[n == 0, 0, 2^n - 2*Binomial[n-1, Floor[(n-1)/2]]];
Array[a, 36, 0] (* Jean-François Alcover, May 05 2019 *)
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Robert FERREOL, Apr 27 2019
STATUS
approved