A063886 - OEIS

%I #125 Jun 17 2024 08:51:06

%S 1,2,2,4,6,12,20,40,70,140,252,504,924,1848,3432,6864,12870,25740,

%T 48620,97240,184756,369512,705432,1410864,2704156,5408312,10400600,

%U 20801200,40116600,80233200,155117520,310235040,601080390,1202160780

%N Number of n-step walks on a line starting from the origin but not returning to it.

%C A Chebyshev transform of A007877(n+1). The g.f. is transformed to (1+x)/((1-x)(1+x^2)) under the mapping G(x)->(1/(1+x^2))G(1/(1+x^2)). - _Paul Barry_, Oct 12 2004

%C a(n-1) = 2*C(n-2, floor((n-2)/2)) is also the number of bit strings of length n in which the number of 00 substrings is equal to the number of 11 substrings. For example, when n = 4 we have 4 such bit strings: 0011, 0101, 1010, and 1100. - _Angel Plaza_, Apr 23 2009

%C Hankel transform is A120617. - _Paul Barry_, Aug 10 2009

%C The Hankel transform of a(n) is (-2)^C(n+1,2). The Hankel transform of (-1)^C(n+1,2)*a(n) is (-1)^C(n+1,2)*A164584(n). - _Paul Barry_, Aug 17 2009

%C For n > 1, a(n) is also the number of n-step walks starting from the origin and returning to it exactly once. - _Geoffrey Critzer_, Jan 24 2010

%C -a(n) is the Z-sequence for the Riordan array A130777. (See the W. Lang link under A006232 for A- and Z-sequences for Riordan matrices). - _Wolfdieter Lang_, Jul 12 2011

%C Number of subsets of {1,...,n} in which the even elements appear as often at even positions as at odd positions. - _Gus Wiseman_, Mar 17 2018

%D D. Perrin, A conjecture on rational sequences, pp. 267-274 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990.

%H Alois P. Heinz, <a href="/A063886/b063886.txt">Table of n, a(n) for n = 0..1000</a>

%H Paul Barry, <a href="https://arxiv.org/abs/1912.01124">A Note on Riordan Arrays with Catalan Halves</a>, arXiv:1912.01124 [math.CO], 2019.

%H Emeric Deutsch, <a href="http://www.jstor.org/stable/40391080">Problem 11424</a>, The American Mathematical Monthly, Vol. 116, No. 3 (March 2009), p. 277.

%F G.f.: sqrt((1+2*x)/(1-2*x)).

%F a(n+1) = 2*C(n, floor(n/2)) = 2*A001405(n); a(2n) = C(2n, n) = A000984(n) = 4*a(2n-2)-|A002420(n)| = 4*a(2n-2)-2*A000108(n-1) = 2*A001700(n-1); a(2n+1) = 2*a(2n) = A028329(n).

%F 2*a(n) = A047073(n+1).

%F a(n) = Sum_{k=0..n} abs(A106180(n,k)). - _Philippe Deléham_, Oct 06 2006

%F a(n) = Sum_{k=0..n} (k+1)binomial(n, (n-k)/2) ( 1-cos((k+1)*Pi/2) (1+(-1)^(n-k))/(n+k+2) ). - _Paul Barry_, Oct 12 2004

%F G.f.: 1/(1-2*x/(1+x/(1+x/(1-x/(1-x/(1+x/(1+x/(1-x/(1-x/(1+ ... (continued fraction). - _Paul Barry_, Aug 10 2009

%F G.f.: 1 + 2*x/(G(0)-x+x^2) where G(k)= 1 - 2*x^2 - x^4/G(k+1); (continued fraction, 1-step). - _Sergei N. Gladkovskii_, Aug 10 2012

%F D-finite with recurrence: n*a(n) = 2*a(n-1) + 4*(n-2)*a(n-2). - _R. J. Mathar_, Dec 03 2012

%F From _Sergei N. Gladkovskii_, Jul 26 2013: (Start)

%F G.f.: 1/G(0), where G(k) = 1 - 2*x/(1 + 2*x/(1 + 1/G(k+1) )); (continued fraction).

%F G.f.: G(0), where G(k) = 1 + 2*x/(1 - 2*x/(1 + 1/G(k+1) )); (continued fraction).

%F G.f.: W(0)/2*(1+2*x), where W(k) = 1 + 1/(1 - 2*x/(2*x + (k+1)/(x*(2*k+1))/W(k+1) )), abs(x) < 1/2; (continued fraction). (End)

%F a(n) = 2^n*Product_{k=0..n-1} (k/n + 1/n)^((-1)^k). - _Peter Luschny_, Dec 02 2013

%F G.f.: G(0), where G(k) = 1 + 2*x*(4*k+1)/((2*k+1)*(1+2*x) - (2*k+1)*(4*k+3)*x*(1+2*x)/((4*k+3)*x + (k+1)*(1+2*x)/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jan 19 2014

%F From _Peter Bala_, Mar 29 2024: (Start)

%F a(n) = 2^n * Sum_{k = 0..n} (-1)^(n+k)*binomial(1/2, k)*binomial(- 1/2, n-k) = 2^n * A000246(n)/n!.

%F a(n) = (1/2^n) * binomial(2*n, n) * hypergeom([-1/2, -n], [1/2 - n], -1). (End)

%F E.g.f.: BesselI(0, 2*x)*(1 + x*(2 + Pi)*StruveL(1, 2*x)) - Pi*x*BesselI(1, 2*x)*StruveL(0, 2*x). - _Stefano Spezia_, May 11 2024

%F a(n) = A089849(n) + A138364(n). - _Mélika Tebni_, Jun 17 2024

%e a(4) = 6 because there are six length four walks that do not return to the origin: {-1, -2, -3, -4}, {-1, -2, -3, -2}, {-1, -2, -1, -2}, {1, 2, 1, 2}, {1, 2, 3, 2}, {1, 2, 3, 4}. There are also six such walks that return exactly one time: {-1, -2, -1, 0}, {-1, 0, -1, -2}, {-1, 0, 1, 2}, {1, 0, -1, -2}, {1, 0, 1, 2}, {1, 2, 1, 0}. - _Geoffrey Critzer_, Jan 24 2010

%e The a(5) = 12 subsets in which the even elements appear as often at even positions as at odd positions: {}, {1}, {3}, {5}, {1,3}, {1,5}, {2,4}, {3,5}, {1,2,4}, {1,3,5}, {2,4,5}, {1,2,4,5}. - _Gus Wiseman_, Mar 17 2018

%p seq(seq(binomial(2*j,j)*i, i=1..2),j=0..16); # _Zerinvary Lajos_, Apr 28 2007

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n<2, n+1,

%p        4*a(n-2) +2*(a(n-1) -4*a(n-2))/n)

%p     end:

%p seq(a(n), n=0..40);  # _Alois P. Heinz_, Feb 10 2014

%p # third program:

%p A063886 := series(BesselI(0, 2*x)*(1 + x*2 + x*Pi*StruveL(1, 2*x)) - Pi*x*BesselI(1, 2*x)*StruveL(0, 2*x), x = 0, 34): seq(n!*coeff(A063886, x, n), n = 0 .. 33); # _Mélika Tebni_, Jun 17 2024

%t Table[Length[Select[Map[Accumulate, Strings[{-1, 1}, n]], Count[ #, 0] == 0 &]], {n, 0, 20}] (* _Geoffrey Critzer_, Jan 24 2010 *)

%t CoefficientList[Series[Sqrt[(1+2x)/(1-2x)],{x,0,40}],x] (* _Harvey P. Dale_, Apr 28 2016 *)

%o (Python)

%o from math import ceil

%o from sympy import binomial

%o def a(n):

%o     if n==0: return 1

%o     return 2*binomial(n-1,(n-1)//2)

%o print([a(n) for n in range(18)])

%o # _David Nacin_, Feb 29 2012

%o (PARI) a(n)=(n==0)+2*binomial(n-1,(n-1)\2)

%o (PARI) a(n) = 2^n*prod(k=0,n-1,(k/n+1/n)^((-1)^k)); \\ _Michel Marcus_, Dec 03 2013

%o (Magma) [1] cat [2*Binomial(n-1, Floor((n-1)/2)): n in [1..40]]; // _G. C. Greubel_, Jun 07 2023

%o (SageMath) [2*binomial(n-1, (n-1)//2) + int(n==0) for n in range(41)] # _G. C. Greubel_, Jun 07 2023

%Y Apart from initial terms, same as A182027.

%Y Cf. A000108, A000246, A000712, A000984, A001405, A001700, A002420, A006232, A007877, A026010, A028329, A045931, A047073, A089849, A097613, A106180, A120617, A130777, A130780, A138364, A164584, A171966, A239241, A300787, A300788, A300789.

%Y Cf. A307768 (complementary event).

%K nonn,walk

%O 0,2

%A _Henry Bottomley_, Aug 28 2001