cp's OEIS Frontend

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

%I A307768 #59 Jun 19 2024 09:37:45
%S A307768 0,0,2,4,10,20,44,88,186,372,772,1544,3172,6344,12952,25904,52666,
%T A307768 105332,213524,427048,863820,1727640,3488872,6977744,14073060,
%U A307768 28146120,56708264,113416528,228318856,456637712,918624304,1837248608,3693886906,7387773812,14846262964,29692525928
%N A307768 Number of n-step random walks on a line starting from the origin and returning to it at least once.
%C A307768 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.
%C A307768 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.
%H A307768 Robert Israel, <a href="/A307768/b307768.txt">Table of n, a(n) for n = 0..3318</a>
%H A307768 Monique Laurent, Sven Polak, and Luis Felipe Vargas, <a href="https://arxiv.org/abs/2302.08886">Semidefinite approximations for bicliques and biindependent pairs</a>, arXiv:2302.08886 [math.CO], 2023.
%F A307768 a(n) = 2^n - A063886(n).
%F A307768 a(n+1) = 2*A045621(n) = 2*(2^n - binomial(n,floor(n/2))).
%F A307768 a(2n) = 2^(2n) - binomial(2n,n); a(2n+1) = 2*a(2n).
%F A307768 G.f.: (1-sqrt(1-4*x^2))/(1-2*x). - _Alois P. Heinz_, May 05 2019
%F A307768 n*(a(n)-2*a(n-1)) - 4*(n-3)*(a(n-2)-2*a(n-3)) = 0. - _Robert Israel_, May 06 2019
%F A307768 a(2n+2) - 2*a(2n+1) = A284016(n) = 2*Catalan(n). - _Robert FERREOL_, Aug 26 2019
%F A307768 From _Mélika Tebni_, Jun 19 2024: (Start)
%F A307768 E.g.f.: exp(2*x) - Integral_{x=-oo..oo} (1/x + 2)*BesselI(1, 2*x) dx - BesselI(1, 2*x).
%F A307768 a(n) = 2*(A027306(n) - A128014(n)). (End)
%e A307768 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].
%e A307768 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].
%p A307768 b:=n->piecewise(n mod 2 = 0,binomial(n,n/2),2*binomial(n-1,(n-1)/2)):
%p A307768 seq(2^n-b(n),n=0..20);
%p A307768 # second program:
%p A307768 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
%t A307768 a[n_] := If[n == 0, 0, 2^n - 2*Binomial[n-1, Floor[(n-1)/2]]];
%t A307768 Array[a, 36, 0] (* _Jean-François Alcover_, May 05 2019 *)
%Y A307768 Cf. A027306, A063886, A045621, A128014, A284016.
%K A307768 nonn,walk
%O A307768 0,3
%A A307768 _Robert FERREOL_, Apr 27 2019