login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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.: (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 * A297183 A232466 A003407

Adjacent sequences:  A307765 A307766 A307767 * A307769 A307770 A307771

KEYWORD

nonn,walk

AUTHOR

Robert FERREOL, Apr 27 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 4 20:38 EST 2021. Contains 341803 sequences. (Running on oeis4.)