|
%I #116 Apr 01 2024 10:32:00
%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 G.f.: 1/G(0), where G(k) = 1 - 2*x/(1 + 2*x/(1 + 1/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jul 26 2013
%F G.f.: G(0), where G(k) = 1 + 2*x/(1 - 2*x/(1 + 1/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jul 26 2013
%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). - _Sergei N. Gladkovskii_, Jul 26 2013
%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)
%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
%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, A000712, A000984, A001405, A001700, A002420, A006232, A007877, A026010, A028329, A045931, A047073, A097613, A106180, A120617, A130777, A130780, A164584, A171966, A239241, A300787, A300788, A300789.
%Y Cf. A307768 (complementary event).
%K nonn,walk
%O 0,2
%A _Henry Bottomley_, Aug 28 2001
|
