A120617 -id:A120617 - cp's OEIS frontend

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

1, 2, 2, 4, 6, 12, 20, 40, 70, 140, 252, 504, 924, 1848, 3432, 6864, 12870, 25740, 48620, 97240, 184756, 369512, 705432, 1410864, 2704156, 5408312, 10400600, 20801200, 40116600, 80233200, 155117520, 310235040, 601080390, 1202160780, 2333606220, 4667212440

Offset: 0

Henry Bottomley, Aug 28 2001

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
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
Hankel transform is A120617. - Paul Barry, Aug 10 2009
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
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
-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
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

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

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
Emeric Deutsch, Problem 11424, The American Mathematical Monthly, Vol. 116, No. 3 (March 2009), p. 277.
D. Perrin, A conjecture on rational sequences, pp. 267-274 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990.

Apart from initial terms, same as A182027.
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.
Cf. A307768 (complementary event).

[1] cat [2*Binomial(n-1, Floor((n-1)/2)): n in [1..40]]; // G. C. Greubel, Jun 07 2023

seq(seq(binomial(2*j,j)*i, i=1..2),j=0..16); # Zerinvary Lajos, Apr 28 2007
# second Maple program:
a:= proc(n) option remember; `if`(n<2, n+1,
       4*a(n-2) +2*(a(n-1) -4*a(n-2))/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 10 2014
# third program:
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

Table[Length[Select[Map[Accumulate, Strings[{-1, 1}, n]], Count[ #, 0] == 0 &]], {n, 0, 20}] (* Geoffrey Critzer, Jan 24 2010 *)
CoefficientList[Series[Sqrt[(1+2x)/(1-2x)],{x,0,40}],x] (* Harvey P. Dale, Apr 28 2016 *)

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

a(n) = 2^n*prod(k=0,n-1,(k/n+1/n)^((-1)^k)); \\ Michel Marcus, Dec 03 2013

from math import ceil
from sympy import binomial
def a(n):
    if n==0: return 1
    return 2*binomial(n-1,(n-1)//2)
print([a(n) for n in range(18)])
# David Nacin, Feb 29 2012

[2*binomial(n-1, (n-1)//2) + int(n==0) for n in range(41)] # G. C. Greubel, Jun 07 2023

G.f.: sqrt((1+2*x)/(1-2*x)).
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).
2*a(n) = A047073(n+1).
a(n) = Sum_{k=0..n} abs(A106180(n,k)). - Philippe Deléham, Oct 06 2006
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
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
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
D-finite with recurrence: n*a(n) = 2*a(n-1) + 4*(n-2)*a(n-2). - R. J. Mathar, Dec 03 2012
From Sergei N. Gladkovskii, Jul 26 2013: (Start)
G.f.: 1/G(0), where G(k) = 1 - 2*x/(1 + 2*x/(1 + 1/G(k+1) )); (continued fraction).
G.f.: G(0), where G(k) = 1 + 2*x/(1 - 2*x/(1 + 1/G(k+1) )); (continued fraction).
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)
a(n) = 2^n*Product_{k=0..n-1} (k/n + 1/n)^((-1)^k). - Peter Luschny, Dec 02 2013
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
From Peter Bala, Mar 29 2024: (Start)
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!.
a(n) = (1/2^n) * binomial(2*n, n) * hypergeom([-1/2, -n], [1/2 - n], -1). (End)
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
a(n) = A089849(n) + A138364(n). - Mélika Tebni, Jun 17 2024
From Amiram Eldar, Aug 15 2025: (Start)
Sum_{n>=0} 1/a(n) = Pi/(3*sqrt(3)) + 2.
Sum_{n>=0} (-1)^n/a(n) = 2/3 + Pi/(9*sqrt(3)). (End)

A082590 Expansion of 1/((1 - 2x)sqrt(1 - 4*x)).

Original entry on oeis.org

1, 4, 14, 48, 166, 584, 2092, 7616, 28102, 104824, 394404, 1494240, 5692636, 21785872, 83688344, 322494208, 1246068806, 4825743832, 18726622964, 72798509728, 283443548276, 1105144970992, 4314388905704, 16862208539008, 65972020761116, 258354647959984, 1012627828868072

Offset: 0

Vladeta Jovovic, May 13 2003

nonn

Row sums of A068555 and A112336. - Paul Barry, Sep 04 2005
Hankel transform is 2^n*(-1)^C(n+1,2) (A120617). - Paul Barry, Apr 26 2009
Number of n-lettered words in the alphabet {1, 2, 3, 4} with as many occurrences of the substring (consecutive subword) [1, 2] as of [1, 3]. - N. J. A. Sloane, Apr 08 2012

Vincenzo Librandi, Table of n, a(n) for n = 0..300
Shalosh B. Ekhad and Doron Zeilberger, Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610 and ANY Problem of That Type, arXiv:1112.6207 [math.CO], 2011. See subpages for rigorous derivations of the g.f., the recurrence, asymptotics for this sequence.
Alejandro Erickson and Frank Ruskey, Enumerating maximal tatami mat coverings of square grids with v vertical dominoes, arXiv:1304.0070 [math.CO], 2013.
Y. Kamiyama, On the middle dimensional homology classes of equilateral polygon spaces, arXiv:1507.03161 [math.AT], 2015.

Bisection of A226302.

Cf. A034430, A068555, A076729, A112336.

A082590 := proc(n)
    coeftayl( 1/(1-2*x)/sqrt(1-4*x),x=0,n) ;
end proc: # R. J. Mathar, Nov 06 2013
A082590 := n -> 2^n*JacobiP(n, 1/2, -1 - n, 3):
seq(simplify(A082590(n)), n = 0..26);  # Peter Luschny, Jan 22 2025

CoefficientList[ Series[ 1/((1 - 2*x)*Sqrt[1 - 4*x]), {x, 0, 25}], x] (* Jean-François Alcover, Mar 26 2013 *)
Table[2^(n) JacobiP[n, 1/2, -1-n, 3], {n, 0, 30}] (* Vincenzo Librandi, May 26 2013 *)

a(n) = 2^n*JacobiP(n, 1/2, -1-n, 3).
A034430(n) = (n!/2^n)*a(n). A076729(n) = n!*a(n).
a(n) = Sum_{k=0..n+1} binomial(2*n+2, k) * sin((n - k + 1)*Pi/2). - Paul Barry, Nov 02 2004
From Paul Barry, Sep 04 2005: (Start)
a(n) = Sum_{k=0..n} 2^(n-k)*binomial(2*k, k).
a(n) = Sum_{k=0..n} (2*k)! * (2*(n-k))!/(n!*k!*(n-k)!). (End)
a(n) = Sum_{k=0..n} C(2*n, n)*C(n, k)/C(2*n, 2*k). - Paul Barry, Mar 18 2007
G.f.: 1/(1 - 4*x + 2*x^2/(1 + x^2/(1 - 4*x + x^2/(1 + x^2/(1 - 4*x + x^2/(1 + ... (continued fraction). - Paul Barry, Apr 26 2009
D-finite with recurrence: n*a(n) + 2*(-3*n+1)*a(n-1) + 4*(2*n-1)*a(n-2) = 0. - R. J. Mathar, Dec 03 2012
a(n) ~ 2^(2*n + 1)/sqrt(Pi*n). - Vaclav Kotesovec, Aug 15 2013
a(n) = 2^(n + 1)*Pochhammer(1/2, n+1)*hyper2F1([1/2,-n], [3/2], -1)/n!. - Peter Luschny, Aug 02 2014
a(n) - 2*a(n-1) = A000984(n). - R. J. Mathar, Apr 24 2024
a(n) = 2^n*JacobiP(n, 1/2, -1 - n, 3). - Peter Luschny, Jan 22 2025

A090132 Expansion of (1+2x)/(1+2x+2*x^2).

Original entry on oeis.org

1, 0, -2, 4, -4, 0, 8, -16, 16, 0, -32, 64, -64, 0, 128, -256, 256, 0, -512, 1024, -1024, 0, 2048, -4096, 4096, 0, -8192, 16384, -16384, 0, 32768, -65536, 65536, 0, -131072, 262144, -262144, 0, 524288, -1048576, 1048576, 0, -2097152, 4194304, -4194304, 0, 8388608

Offset: 0

Paul Barry, Nov 21 2003

The expansion of (1-2x)/(1-2x+2x^2) has a(n) = Sum_{k=0..n} C(n,k)(-1)^(-k)(-1)^floor(k/2).

Pisano period lengths: 1, 1, 8, 1, 4, 8, 24, 1, 24, 4, 40, 8, 12, 24, 8, 1, 16, 24, 72, 4, ... - R. J. Mathar, Aug 10 2012

			G.f. = 1 - 2*x^2 + 4*x^3 - 4*x^4 + 8*x^6 - 16*x^7 + 16*x^8 - 32*x^10 + 64*x^11 + ...

Index entries for linear recurrences with constant coefficients, signature (-2,-2).

Cf. A009116.

Cf. A135353, A137444, A137426, A137429.

a[ n_] := Re[ -(I - 1)^(n + 1)]; (* Michael Somos, May 25 2013 *)
a[ n_] := If[ n < 0, - 2^(n-1) a[2 - n], SeriesCoefficient[ (1 + 2 x) / (1 + 2 x + 2 x^2), {x, 0, n}]]; (* Michael Somos, May 25 2013 *)
a[ n_] := If[ n < 0, - 2^(n-1) a[2 - n], n! SeriesCoefficient[ (Cos[x] + Sin[x]) / Exp[x], {x, 0, n}]]; (* Michael Somos, May 25 2013 *)
a[ n_] := Simplify[ -2 Sqrt[2]^(n - 1) ChebyshevT[ n + 1, -1 / Sqrt[2]]]; (* Michael Somos, May 25 2013 *)
LinearRecurrence[{-2,-2},{1,0},50] (* Harvey P. Dale, Oct 23 2017 *)

my(x='x+O('x^66)); Vec(serlaplace((cos(x)+sin(x))/exp(x))) \\ Joerg Arndt, May 13 2011

vector(66, n, -real((-1+I)^n)) /* Joerg Arndt, May 13 2011 */

{a(n) = real( -(I - 1)^(n + 1) )}; /* Michael Somos, May 25 2013 */

{a(n) = if( n<0, - 2^(n-1) * a(2 - n), polcoeff( (1 + 2*x) / (1 + 2*x + 2*x^2) + x * O(x^n), n))}; /* Michael Somos, May 25 2013 */

{a(n) = my(A); if( n<0, - 2^(n-1) * a(2 - n), A = x * O(x^n); n! * polcoeff( (cos(x + A) + sin(x + A)) / exp(x + A), n))}; /* Michael Somos, May 25 2013 */

{a(n) = simplify( -2 * quadgen(8)^(n - 1) * polchebyshev( n + 1, 1, -1 / quadgen(8)))}; /* Michael Somos, May 25 2013 */

G.f.: (1+2*x)/(1+2*x+2*x^2).
a(n) = Sum_{k=0..n} C(n, k)*(-1)^(n-k)*(-1)^floor(k/2).
a(n) = sqrt(2)*2^(n/2)*sin(3*Pi*n/4+Pi/4). - Paul Barry, Feb 25 2004
a(n) = -a(n-1) + 2*a(n-3). - Paul Curtz, Apr 24 2008
Negated real part of (-1+i)^n, imaginary part is A108520. - Joerg Arndt, May 13 2011
From Sergei N. Gladkovskii, Nov 28 2011: (Start)
E.g.f.: (cos(x) + sin(x))/exp(x).
E.g.f.: A(x) = Q(0), where Q(k)=1-(x^2)/((4*k+1)*(2*k+1)+2*x*(4*k+1)*(2*k+1)/(4*k+3-2*x-x*(4*k+3)/(x-(4*k+4)/Q(k+1)))); (continued fraction). (End)
a(4*n + 1) = 0. a(2*n) = A120617(n). a(4*n + 3) = (-4)^n. - Michael Somos, May 25 2013
a(n) = - 2^(n-1)*a(2-n) for all n in Z. - Michael Somos, Jun 26 2017
a(n) = (I + 1)*((-1 - I)^n - I*(-1 + I)^n)/2. - Taras Goy, Apr 20 2019

A126966 Expansion of sqrt(1 - 4x)/(1 - 2x).

Original entry on oeis.org

1, 0, -2, -8, -26, -80, -244, -752, -2362, -7584, -24892, -83376, -284324, -984672, -3455144, -12259168, -43908026, -158531392, -576352364, -2107982128, -7750490636, -28629222112, -106190978264, -395347083808, -1476813394916, -5533435084480, -20790762971864, -78316232088032

Offset: 0

N. J. A. Sloane, Mar 22 2007

sign

Hankel transform is 2^n*(-1)^binomial(n+1, 2) = A120617(n). - Paul Barry, Feb 08 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A000108, A028329, A082590, A126967.

List([0..30], n-> (-1)*Sum([0..n], j-> 2^j*Binomial(2*(n-j), n-j)/(2*(n-j) -1) )); # G. C. Greubel, Jan 29 2020

R:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( Sqrt(1-4*x)/(1-2*x) )); // G. C. Greubel, Jan 29 2020

a := n -> -add(2^j*binomial(2*n-2*j,n-j)/(2*n-2*j-1), j=0..n):
seq(a(n),n=0..30); # Emeric Deutsch, Mar 25 2007
# second Maple program:
CatalanNumber := n -> binomial(2*n, n)/(n+1):
a := n -> 2^n*I + CatalanNumber(n)*simplify(hypergeom([1, n + 1/2], [n + 2], 2)):
seq(a(n), n=0..26); # Peter Luschny, Aug 04 2020
# third program:
A126966 := n -> 2*binomial(2*n, n) - add(2^(n-k)*binomial(2*k,k), k=0..n):
seq(A126966(n), n = 0 .. 27); # Mélika Tebni, Mar 08 2024

CoefficientList[Series[Sqrt[1-4*x]/(1-2*x), {x,0,30}], x] (* G. C. Greubel, Jan 31 2017 *)

Vec(sqrt(1-4*x)/(1-2*x) + O(x^30)) \\ G. C. Greubel, Jan 31 2017

def A126966_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( sqrt(1-4*x)/(1-2*x) ).list()
A126966_list(30) # G. C. Greubel, Jan 29 2020

a(n) = -Sum_{j=0..n} ( 2^j*binomial(2n-2j, n-j)/(2n-2j-1) ). - Emeric Deutsch, Mar 25 2007
D-finite with recurrence: n*a(n) + 6*(1-n)*a(n-1) + 4*(2*n-3)*a(n-2) = 0. - R. J. Mathar, Nov 14 2011, corrected Feb 17 2020
a(n) ~ -4^n/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Jun 29 2013
a(n) = 2^n*i + CatalanNumber(n)*hypergeom([1, n + 1/2], [n + 2], 2). - Peter Luschny, Aug 04 2020
a(n) = A028329(n) - A082590(n). - Mélika Tebni, Mar 08 2024

A137720 Expansion of sqrt(1-4x)/(1-3x).

Original entry on oeis.org

1, 1, 1, -1, -13, -67, -285, -1119, -4215, -15505, -56239, -202309, -724499, -2589521, -9254363, -33111969, -118725597, -426892131, -1539965973, -5575175319, -20260052337, -73908397851, -270657727593, -994938310059

Offset: 0

Paul Barry, Feb 08 2008

Hankel transform is A120617. In general, sqrt(1-4*x)/(1-k*x) has Hankel transform with g.f. of (1-2*x)/(1+2*(k+2)*x+4*x^2).

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A126966, A106191, A157674.

CoefficientList[Series[Sqrt[1-4*x]/(1-3*x), {x, 0, 20}], x] (* Vaclav Kotesovec, Jul 31 2014 *)
FullSimplify[Table[I*3^(-1/2+n) + 2^(1+2*n)*Gamma[1/2+n] * Hypergeometric2F1Regularized[1, 1/2+n, 2+n, 4/3]/(3*Sqrt[Pi]), {n, 0, 20}]] (* Vaclav Kotesovec, Jul 31 2014 *)

x='x+O('x^50); Vec(sqrt(1-4*x)/(1-3*x)) \\ G. C. Greubel, Mar 21 2017

a(n) = Sum_{k=0..n} 3^k*C(2*n-2*k,n-k)/(1-(2*n-2*k)).
D-finite with recurrence: n*a(n) + (6-7*n)*a(n-1) + 6*(2*n-3)*a(n-2) = 0. - R. J. Mathar, Nov 16 2011
a(n) ~ -2^(2*n+1) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jul 31 2014
a(n) = (-1)^n * A157674(2*n+1). - Vaclav Kotesovec, Jul 31 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

A082590 Expansion of 1/((1 - 2*x)*sqrt(1 - 4*x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A090132 Expansion of (1+2*x)/(1+2*x+2*x^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

PARI

PARI

Formula

A126966 Expansion of sqrt(1 - 4*x)/(1 - 2*x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A137720 Expansion of sqrt(1-4*x)/(1-3*x).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A082590 Expansion of 1/((1 - 2x)sqrt(1 - 4*x)).

A090132 Expansion of (1+2x)/(1+2x+2*x^2).

A126966 Expansion of sqrt(1 - 4x)/(1 - 2x).

A137720 Expansion of sqrt(1-4x)/(1-3x).