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,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

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]]];
Array[a, 36, 0] (* Jean-François Alcover, May 05 2019 *)

Crossrefs

Cf. A063886, A045621.

Sequence in context: A121880 A094536 A323445 * A370583 A297183 A232466

Adjacent sequences: A307765 A307766 A307767 * A307769 A307770 A307771

Keyword

nonn,walk

Author

Robert FERREOL, Apr 27 2019

Status

approved