A138350 -id:A138350 - cp's OEIS frontend

A005558 a(n) is the number of n-step walks on square lattice such that 0 <= y <= x at each step.

1, 1, 3, 6, 20, 50, 175, 490, 1764, 5292, 19404, 60984, 226512, 736164, 2760615, 9202050, 34763300, 118195220, 449141836, 1551580888, 5924217936, 20734762776, 79483257308, 281248448936, 1081724803600, 3863302870000, 14901311070000, 53644719852000

Offset: 0

N. J. A. Sloane

Number of n-step walks that start at the origin, constrained to stay in the first octant (0 <= y <= x). (Conjectured) - Benjamin Phillabaum, Mar 11 2011, corrected by Robert Israel, Oct 07 2015
For n >= 1, a(n-1) is the number of Dyck Paths with semilength n having floor((n+2)/2) U's in odd numbered positions. Example: (U is in odd numbered position and u is in even numbered position) Dyck path with n=5, floor ((5+2)/2)=3: UuddUuUddd. - Roger Ford, May 27 2017
The ratio of the number of n-step walks on the octant with an equal number of North steps and South steps to the total number of n-step walks on the octant is A005817(n)/a(n).  For the reduced ratio, if n is divisible by 4 or n-1 is divisible by 4 the ratio is 1:floor(n/4)+1 and for all other values of n the ratio is 2:floor(n/2)+2.  Example n = 4: A005817(4) = 10; EEEE, EEEW, EEWE, EWEE, EWEW, EEWW, ENSE, ENES, ENSW, EENS; a(4) = 20; 10:20 reduces to 1:2. - Roger Ford, Nov 04 2019

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Slides for Séminaire de Combinatoire Ph. Flajolet, Mar 28 2013.
Alin Bostan, Calcul Formel pour la Combinatoire des Marches [The text is in English], Habilitation à Diriger des Recherches, Laboratoire d'Informatique de Paris Nord, Université Paris 13, December 2017.
Alin Bostan, Frédéric Chyzak, Mark van Hoeij, Manuel Kauers, and Lucien Pech, Hypergeometric expressions for generating functions of walks with small steps in the quarter plane, Eur. J. Comb. 61, 242-275 (2017)
Sergi Elizalde, The degree of symmetry of lattice paths, arXiv:2002.12874 [math.CO], 2020.
R. K. Guy, Letter to N. J. A. Sloane, May 1990
R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6. See Column 1 of Figure 5.
Heinrich Niederhausen, A Note on the Enumeration of Diffusion Walks in the First Octant by Their Number of Contacts with the Diagonal, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.3.

See A138350 for a signed version.
Bisections are A000891 and A000888/2.
Cf. A005559, A005560, A005561, A005562, A093768.
Cf. A000108, A005817. Column y=0 of A052174.

[Binomial(n+1, Ceiling(n/2))*Binomial(n, Floor(n/2)) - Binomial(n+1, Ceiling((n-1)/2))*Binomial(n, Floor((n-1)/2)): n in [0..30]]; // Vincenzo Librandi, Sep 30 2015

A:= proc(n,x,y) option remember;
    local j, xpyp, xp,yp, res;
    xpyp:= [[x-1,y],[x+1,y],[x,y-1],[x,y+1]];
    res:= 0;
    for j from 1 to 4 do
      xp:= xpyp[j,1];
      yp:= xpyp[j,2];
      if xp < 0 or xp > yp or xp + yp > n then next fi;
      res:= res + procname(n-1,xp,yp)
    od;
return res
end proc:
A(0,0,0) := 1:
seq(add(add(A(n,x,y), y = x .. n - x), x = 0 .. floor(n/2)), n = 0 .. 50); # Robert Israel, Oct 07 2015

a[n_] := 1/2*Binomial[2*Floor[n/2]+1, Floor[n/2]+1]*CatalanNumber[1/2*(n+Mod[n, 2])]*(Mod[n, 2]+2); Table[a[n]//Abs, {n, 0, 27}] (* Jean-François Alcover, Mar 13 2014 *)

a(n)=binomial(n+1,ceil(n/2))*binomial(n,floor(n/2)) - binomial(n+1,ceil((n-1)/2))*binomial(n,floor((n-1)/2))

from sympy import ceiling as c, binomial
def a(n):
    return binomial(n + 1, c(n/2))*binomial(n, n//2) - binomial(n + 1, c((n - 1)/2))*binomial(n, (n - 1)//2)
print([a(n) for n in range(51)]) # Indranil Ghosh, Jul 02 2017

a(n) = C(n+1, ceiling(n/2))*C(n, floor(n/2)) - C(n+1, ceiling((n-1)/2))*C(n, floor((n-1)/2)). - Paul D. Hanna, Apr 16 2004
G.f.: (1/(4x^2))*((16*x^2-1)*(hypergeom([1/2, 1/2],[1],16*x^2)+2*x*(4*x-1)*hypergeom([3/2, 3/2],[2],16*x^2))-2*x+1). - Mark van Hoeij, Oct 13 2009
E.g.f (conjectured): BesselI(1,2*x)*(BesselI(0,2*x)+BesselI(1,2*x))/x. - Benjamin Phillabaum, Feb 25 2011
Conjecture: (2*n+1)*(n+3)*(n+2)*a(n) - 4*(2*n^2+4*n+3)*a(n-1) - 16*n*(2*n+3)*(n-1)*a(n-2) = 0. - R. J. Mathar, Apr 02 2017
Conjecture: (n+3)*(n+2)*a(n) - 4*(n^2+3*n+1)*a(n-1) + 16*(-n^2+n+1)*a(n-2) + 64*(n-1)*(n-2)*a(n-3) = 0. - R. J. Mathar, Apr 02 2017
a(n) = Sum_{k=0..floor(n/2)} n!/(k!*k!*(floor(n/2)-k)!*(floor((n+1)/2)-k)!*(k+1)) (conjectured). - Roger Ford, Aug 04 2017
a(n) = A000108(floor((n+1)/2))*A000108(floor(n/2))*(2*(floor(n/2))+1). - Roger Ford, Nov 15 2019
a(n) = Product_{k=3..n} (4*floor((k-1)/2) + 2) / (floor((k+2)/2)). - Roger Ford, Apr 29 2024

A210736 Expansion of (1 + sqrt( (1 + 2x) / (1 - 2x))) / 2 in powers of x.

Original entry on oeis.org

1, 1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, 924, 1716, 3432, 6435, 12870, 24310, 48620, 92378, 184756, 352716, 705432, 1352078, 2704156, 5200300, 10400600, 20058300, 40116600, 77558760, 155117520, 300540195, 601080390, 1166803110, 2333606220, 4537567650

Offset: 0

Michael Somos, May 10 2012

nonn

Hankel transform is period 4 sequence [ 1, 0, -1, 0, ...] A056594 and the Hankel transform of sequence omitting a(0) is the all 1s sequence A000012. This is the unique sequence with that property.
Series reversion of x*A(x) apparently yields x*A036765(-x). - R. J. Mathar, Sep 24 2012
a(n) is the number of length n words on {-1,1} such that the sum of any of its prefixes is always positive.  Cf. A001405 where the sum of all prefixes is nonnegative. - Geoffrey Critzer, Jul 08 2013

			G.f. = 1 + x + x^2 + 2*x^3 + 3*x^4 + 6*x^5 + 10*x^6 + 20*x^7 + 35*x^8 + 70*x^9 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Jean-Luc Baril and José L. Ramírez, Knight's paths towards Catalan numbers, Univ. Bourgogne Franche-Comté (2022).
Paul Barry, d-orthogonal polynomials, Fuss-Catalan matrices and lattice paths, arXiv:2505.16718 [math.CO], 2025. See p. 25.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; page 77.

Essentially the same as A001405.
Cf. A056594, A138350, A210628, A211278.
Cf. A000108, A091867, A146559, A126930.

nn=36; d=(1-(1-4x^2)^(1/2))/(2x^2);CoefficientList[Series[1/(1-x d),{x,0,nn}],x] (* Geoffrey Critzer, Jul 08 2013 *)
CoefficientList[Series[2 x / (-1 + 2 x + Sqrt[1 - 4 x^2]), {x, 0, 40}], x] (* Vincenzo Librandi, Nov 10 2014 *)

{a(n) = if( n<1, n==0, binomial( n - 1, (n - 1)\2))};

{a(n) = polcoeff( (1 + sqrt( (1 + 2*x) / (1 - 2*x) + x * O(x^n))) / 2, n)};

G.f.: 2 * x / (-1 + 2*x + sqrt(1 - 4*x^2)).
G.f. A(x) satisfies A(x) = A(x)^2 - x / (1 - 2*x).
G.f. A(x) satisfies A( x / (1 + x^2) ) = 1 / (1 - x).
G.f. A(x) satisfies A(1/3) = (1 + sqrt(5))/2.
G.f. A(x) = 1 + x / (1 - 2*x + x / A(x)).
G.f. A(x) = 1 + x / (1 - x / (1 - x / (1 + x / A(x)))).
G.f. A(x) = 1 + x * A001405(x). a(n+1) = A001405(n).
Convolution inverse is A210628. Partial sums is A072100.
Binomial transform with offset 1 is A211278 with offset 1. a(n+2) * a(n) - a(n+1)^2 = A138350(n-1).
a(n) = (-1)^floor(n/2)*hypergeom2F1([1-n, -n],[1],-1). - Peter Luschny, Sep 01 2012
D-finite with recurrence: n*a(n) -2*a(n-1) +4*(2-n)*a(n-2)=0. - R. J. Mathar, Sep 14 2012
G.f. A(x) = 1 / (1 - x / (1 - x^2 / (1 - x^2 / (1 - x^2 / ...)))). - Michael Somos, Jan 02 2013
G.f.: 1/(1 - x*C(x)) where C(x) is the o.g.f. for A126120. - Geoffrey Critzer, Jul 08 2013
a(n) ~ 2^(n-1/2) / sqrt(Pi*n). - Vaclav Kotesovec, Feb 01 2014
G.f.: A(x) = 1 - x/(- 1 + x/A(-x)). - Arkadiusz Wesolowski, Feb 28 2014
From Tom Copeland, Nov 07 2014: (Start)
Setting a(0)=0 here, we have a signed version in A126930 and
O.g.f. G(x)=[-1+sqrt(1+4*x/(1-2x))]/2 = x + x^2 + 2 x^3 + ... = -C[-P(P(x,-1),-1)]= -C[-P(x,-2)] where C(x)= [1-sqrt(1-4*x)]/2= x + x^2 + 2 x^3 + ... = A000108(x) with inverse Cinv(x)=x*(1-x), and P(x,t)= x/(1 + t*x) with inverse P(x,-t).
These types of arrays are from linear fractional transformations of C(x). See A091867.
Ginv(x) = P[-Cinv(-x),2] = x*(1+x)/(1+2*x*(1-x))= (x+x^2)/(1+2(x+x^2)) (see A146559). (End)

A138351 Central moment sequence of tr(A^2) in USp(4).

Original entry on oeis.org

1, 0, 2, 1, 11, 16, 95, 232, 1085, 3460, 14820, 54275, 227095, 895688, 3756688, 15462293, 65586405, 277342336, 1192038266, 5136760581, 22357937431, 97730561480, 430177280197, 1901975209706, 8454151507801, 37734802709796

Offset: 0

Andrew V. Sutherland, Mar 16 2008, Mar 31 2008

nonn

If A is a random matrix in the compact group USp(4) (4 X 4 complex matrices which are unitary and symplectic), then a(n) = E[(tr(A^2)+1)^n] is the n-th central moment of the trace of A^2, since E[tr(A^2)] = -1 (see A138350).

			a(4) = 11 because E[(tr(A^2)+1)^4] = 11 for a random matrix A in USp(4).
a(4) = 1*A138350(0)+4*A138350(1)+6*A138350(2)+4*A138350(3)+1*A138350(4) = 1*1 + 4*(-1) + 6*3 + 4*(-6) + 1*20 = 11.

Kiran S. Kedlaya and Andrew V. Sutherland, Hyperelliptic curves, L-polynomials and random matrices, arXiv:0803.4462 [math.NT], 2008-2010.
Kiran S. Kedlaya and Andrew V. Sutherland, Hyperelliptic curves, L-polynomials and random matrices, in Arithmetic, Geometry, Cryptography, and Coding Theory: International Conference, November 5-9, 2007, CIRM, Marseilles, France. Gilles Lachaud, Christophe Ritzenthaler, Michael A. Tsfasman, editors. 2009. (Contemporary Mathematics ; v.487)..

Cf. A138350.

a126120[n_] := If[EvenQ[n], CatalanNumber[n/2], 0];
a138364[n_] := If[EvenQ[n], 0, Binomial[n, Floor[n/2]], 0];
a138350[n_] := a126120[n] a138364[n+1] - a138364[n] a126120[n+1];
a[n_] := Sum[Binomial[n, i] a138350[i], {i, 0, n}];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 13 2018 *)

a(n) = (1/2)Integral_{x=0..Pi,y=0..Pi}(2cos(2x)+2cos(2y)+1)^n(2cos(x)-2cos(y))^2(2/Pi*sin^2(x))(2/Pi*sin^2(y))dxdy.

a(n) = Sum_{i=0..n} binomial(n,i)*A138350(i).

cp's OEIS Frontend

A005558 a(n) is the number of n-step walks on square lattice such that 0 <= y <= x at each step.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A210736 Expansion of (1 + sqrt( (1 + 2x) / (1 - 2x))) / 2 in powers of x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A138351 Central moment sequence of tr(A^2) in USp(4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

cp's OEIS Frontend

A005558 a(n) is the number of n-step walks on square lattice such that 0 <= y <= x at each step.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

A210736 Expansion of (1 + sqrt( (1 + 2*x) / (1 - 2*x))) / 2 in powers of x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A138351 Central moment sequence of tr(A^2) in USp(4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A210736 Expansion of (1 + sqrt( (1 + 2x) / (1 - 2x))) / 2 in powers of x.