A307768 Number of n-step random walks on a line starting from the origin and returning to it at least once.

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

Offset: 0

Author

Robert FERREOL, Apr 27 2019

Keywords

• nonn
• walk

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.

Examples

			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].
		

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.

Crossrefs

Cf. A027306, A063886, A045621, A128014, A284016.

Programs

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 *)

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).

a(n) = 2*(A027306(n) - A128014(n)). (End)