A052174 -id:A052174 - cp's OEIS frontend

A005560 Number of walks on square lattice. Column y=2 of A052174.

1, 3, 15, 45, 189, 588, 2352, 7560, 29700, 98010, 382239, 1288287, 5010005, 17177160, 66745536, 232092432, 901995588, 3173688180, 12342120700, 43861998180, 170724392916, 611947174608, 2384209771200, 8609646396000, 33577620944400, 122041737663300, 476432168185575

Offset: 2

N. J. A. Sloane

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

Vincenzo Librandi, Table of n, a(n) for n = 2..1000
R. K. Guy, Letter to N. J. A. Sloane, May 1990
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6, w_n'(2).

Cf. A005558, A005559, A005561, A005562, A093768.

Cf. A052174.

[Binomial(n+3, Ceiling(n/2))*Binomial(n+2, Floor(n/2)) - Binomial(n+3, Ceiling((n-1)/2))*Binomial(n+2, Floor((n-1)/2)): n in [0..30]]; // Vincenzo Librandi, Apr 03 2017

wnprime := proc(n,y)
    local k;
    if type(n-y,'even') then
        k := (n-y)/2 ;
        binomial(n+1,k)*(binomial(n,k)-binomial(n,k-1)) ;
    else
        k := (n-y-1)/2 ;
        binomial(n+1,k)*binomial(n,k+1)-binomial(n+1,k+1)*binomial(n,k-1) ;
    end if;
end proc:
A005560 := proc(n)
    wnprime(n,2) ;
end proc:
seq(A005560(n),n=2..20) ; # R. J. Mathar, Apr 02 2017

Table[Binomial[n+3, Ceiling[n/2]] Binomial[n+2, Floor[n/2]]-Binomial[n+3, Ceiling[(n-1)/2]] Binomial[n+2, Floor[(n-1)/2]], {n, 0, 30}] (* Vincenzo Librandi, Apr 03 2017 *)

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

a(n) = C(n+3, ceiling(n/2))*C(n+2, floor(n/2)) - C(n+3, ceiling((n-1)/2))*C(n+2, floor((n-1)/2)). - Paul D. Hanna, Apr 16 2004

Conjecture: (n-1)*(n-2)*(2*n+1)*(n+5)*(n+4)*a(n) -4*n*(n+1)*(2*n^2+4*n+19)*a(n-1) -16*n^2*(n-1)*(2*n+3)*(n+1)*a(n-2)=0. - R. J. Mathar, Apr 02 2017

A005559 Number of walks on square lattice. Column y=1 of A052174.

Original entry on oeis.org

1, 2, 8, 20, 75, 210, 784, 2352, 8820, 27720, 104544, 339768, 1288287, 4294290, 16359200, 55621280, 212751396, 734959368, 2821056160, 9873696560, 38013731756, 134510127752, 519227905728, 1854385377600, 7174705330000, 25828939188000, 100136810390400

Offset: 1

N. J. A. Sloane

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

R. K. Guy, Letter to N. J. A. Sloane, May 1990
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6 (see figure 5).

Cf. A005558-A005560, A093768.

Cf. A052174.

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

seq(binomial(n+1, ceil((n-1)/2))*binomial(n, floor((n-1)/2)) -binomial(n+1, ceil((n-2)/2))*binomial(n, floor((n-2)/2)), n=1..30); # Robert Israel, Oct 19 2014

Table[Binomial[n+2, Ceiling[n/2]] Binomial[n+1, Floor[n/2]] - Binomial[n+2, Ceiling[(n-1)/2]] Binomial[n+1, Floor[(n-1)/2]], {n, 0, 200}] (* Vincenzo Librandi, Oct 17 2014 *)

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

a(n) = C(n+1,ceiling((n-1)/2)) *C(n,floor((n-1)/2)) -C(n+1,ceiling((n-2)/2)) *C(n,floor((n-2)/2)). - Paul D. Hanna, Apr 16 2004
G.f.: -(48*x^3-16*x^2-3*x+1)*EllipticK(4*x)/(12*Pi*x^4)+(4*x^2-9*x+1)*EllipticE(4*x)/(12*Pi*x^4)+1/(4*x^3)-1/(2*x^2) (using Maple's convention for elliptic integrals: EllipticE(t) = Integral_{s=0..1} sqrt(1 - s^2*t^2)/sqrt(1-s^2) ds, EllipticK(t) = Integral_{s=0..1} ((1-s^2*t^2)*(1-s^2))^(-1/2) ds). - Robert Israel, Oct 19 2014
Conjecture: -(n-1)*(2*n+1)*(n+4)*(n+3)*a(n) +4*(n+1)*(2*n^2+4*n+9)*a(n-1) +16*n*(n-1)*(2*n+3)*(n+1)*a(n-2)=0. - R. J. Mathar, Apr 02 2017

A005561 Number of walks on square lattice. Column y=3 of A052174.

Original entry on oeis.org

1, 4, 24, 84, 392, 1344, 5760, 19800, 81675, 283140, 1145144, 4008004, 16032016, 56632576, 225059328, 801773856, 3173688180, 11392726800, 44986664800, 162594659920, 641087516256, 2331227331840, 9183622822400, 33577620944400, 132211882468575, 485773975404900

Offset: 3

N. J. A. Sloane

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

Vincenzo Librandi, Table of n, a(n) for n = 3..1000
R. K. Guy, Letter to N. J. A. Sloane, May 1990
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6. See w_n'(3).

Cf. A005558, A005559, A005560, A005562, A093768.

Cf. A052174.

[Binomial(n+4, Ceiling(n/2))*Binomial(n+3, Floor(n/2)) - Binomial(n+4, Ceiling((n-1)/2))*Binomial(n+3, Floor((n-1)/2)): n in [0..30]]; // Vincenzo Librandi, Apr 03 2017

wnprime := proc(n,y)
    local k;
    if type(n-y,'even') then
        k := (n-y)/2 ;
        binomial(n+1,k)*(binomial(n,k)-binomial(n,k-1)) ;
    else
        k := (n-y-1)/2 ;
        binomial(n+1,k)*binomial(n,k+1)-binomial(n+1,k+1)*binomial(n,k-1) ;
    end if;
end proc:
A005561 := proc(n)
    wnprime(n,3) ;
end proc:
seq(A005561(n),n=3..30) ; # R. J. Mathar, Apr 02 2017

Table[Binomial[n+4, Ceiling[n/2]] Binomial[n+3, Floor[n/2]]-Binomial[n+4, Ceiling[(n-1)/2]] Binomial[n+3, Floor[(n-1)/2]], {n, 0, 30}] (* Vincenzo Librandi, Apr 03 2017 *)

{a(n)=binomial(n+4,ceil(n/2))*binomial(n+3,floor(n/2)) - binomial(n+4,ceil((n-1)/2))*binomial(n+3,floor((n-1)/2))}

a(n) = C(n+4, ceiling(n/2))*C(n+3, floor(n/2)) - C(n+4, ceiling((n-1)/2))*C(n+3, floor((n-1)/2)). - Paul D. Hanna, Apr 16 2004

Conjecture: (n-2)*(n-3)*(2*n+1)*(n+6)*(n+5)*a(n) - 4*n*(n+1)*(2*n^2+4*n+33)*a(n-1) - 16*n^2*(n-1)*(2*n+3)*(n+1)*a(n-2) = 0. - R. J. Mathar, Apr 02 2017

A005562 Number of walks on square lattice. Column y=4 of A052174.

Original entry on oeis.org

1, 5, 35, 140, 720, 2700, 12375, 45375, 196625, 715715, 3006003, 10930920, 45048640, 164105760, 668144880, 2441298600, 9859090500, 36149998500, 145173803500, 534239596880, 2136958387520, 7892175863000, 31479019635375, 116657543354625, 464342770607625, 1726402608669375

Offset: 4

N. J. A. Sloane

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

Vincenzo Librandi, Table of n, a(n) for n = 4..1000
R. K. Guy, Letter to N. J. A. Sloane, May 1990
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6, w_n'(4).

Cf. A005558, A005559, A005560, A005561, A093768.

Cf. A052174.

[Binomial(n+5, Ceiling(n/2))*Binomial(n+4, Floor(n/2)) - Binomial(n+5, Ceiling((n-1)/2))*Binomial(n+4, Floor((n-1)/2)): n in [0..30]]; // Vincenzo Librandi, Apr 03 2017

wnprime := proc(n,y)
    local k;
    if type(n-y,'even') then
        k := (n-y)/2 ;
        binomial(n+1,k)*(binomial(n,k)-binomial(n,k-1)) ;
    else
        k := (n-y-1)/2 ;
        binomial(n+1,k)*binomial(n,k+1)-binomial(n+1,k+1)*binomial(n,k-1) ;
    end if;
end proc:
A005562 := proc(n)
    wnprime(n,4) ;
end proc:
seq(A005562(n),n=4..30) ; # R. J. Mathar, Apr 02 2017

Table[Binomial[n+5, Ceiling[n/2]] Binomial[n+4, Floor[n/2]]-Binomial[n+5, Ceiling[(n-1)/2]] Binomial[n+4, Floor[(n-1)/2]], {n, 0, 30}] (* Vincenzo Librandi, Apr 03 2017 *)

{a(n)=binomial(n+5,ceil(n/2))*binomial(n+4,floor(n/2)) - binomial(n+5,ceil((n-1)/2))*binomial(n+4,floor((n-1)/2))}

a(n) = C(n+5, ceiling(n/2))*C(n+4, floor(n/2)) - C(n+5, ceiling((n-1)/2))*C(n+4, floor((n-1)/2)). - Paul D. Hanna, Apr 16 2004

Conjecture: (n-3)*(n-4)*(2*n+1)*(n+7)*(n+6)*a(n) - 4*n*(n+1)*(2*n^2+4*n+51)*a(n-1) - 16*n^2*(n-1)*(2*n+3)*(n+1)*a(n-2) = 0. - R. J. Mathar, Apr 02 2017

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

Original entry on oeis.org

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

A093768 Positive first differences of the rows of triangle A088459, which enumerates symmetric Dyck paths.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 8, 6, 1, 4, 15, 20, 20, 1, 5, 24, 45, 75, 50, 1, 6, 35, 84, 189, 210, 175, 1, 7, 48, 140, 392, 588, 784, 490, 1, 8, 63, 216, 720, 1344, 2352, 2352, 1764, 1, 9, 80, 315, 1215, 2700, 5760, 7560, 8820, 5292, 1, 10, 99, 440, 1925, 4950, 12375, 19800

Offset: 0

Paul D. Hanna, Apr 16 2004

Suggested by Bozydar Dubalski (slawb(AT)atr.bydgoszcz.pl). Related to walks on a square lattice: main diagonal forms A005558, secondary diagonals form A005559, A005560, A005561, A005562, A005563.

Apparently row-reversed version of A052174. - R. J. Mathar, Feb 03 2025

			1;
1, 1;
1, 2, 3;
1, 3, 8, 6;
1, 4, 15, 20, 20;
1, 5, 24, 45, 75, 50;
1, 6, 35, 84, 189, 210, 175;

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Cf. A088459, A005558-A005562, A005563 (column 3), A005564 (column 4), A005565 (column 5), A005566 (row sums).

A093768 := proc(n,k)
    if k = 0 then
        A088459(n,k);
    else
        A088459(n,k)-A088459(n,k-1);
    end if;
end proc:
seq(seq(A093768(n,k),k=0..n-1),n=1..10) ; # R. J. Mathar, Apr 02 2017

T[n_, k_] := Binomial[n + 1, Ceiling[k/2]]*Binomial[n, Floor[k/2]] - Binomial[n + 1, Ceiling[(k - 1)/2]]*Binomial[n, Floor[(k - 1)/2]]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* G. C. Greubel, Oct 25 2017 *)

{T(n,k) =binomial(n+1,ceil(k/2))*binomial(n,floor(k/2)) -binomial(n+1,ceil((k-1)/2))*binomial(n,floor((k-1)/2))}

T(n, k) = C(n+1, ceiling(k/2))*C(n, floor(k/2)) - C(n+1, ceiling((k-1)/2))*C(n, floor((k-1)/2)) for n>=k>=0.

A379822 Triangle read by rows: T(n, k) is the number of walks of length n on the Z X Z grid with unit steps in all four directions (NSWE) starting at (0, 0), and ending on the vertical line x = 0 if k = 0, or on the line x = k or x = -(n + 1 - k) if k > 0.

Original entry on oeis.org

1, 2, 2, 6, 5, 5, 20, 16, 12, 16, 70, 57, 36, 36, 57, 252, 211, 130, 90, 130, 211, 924, 793, 507, 286, 286, 507, 793, 3432, 3004, 2016, 1092, 728, 1092, 2016, 3004, 12870, 11441, 8024, 4488, 2380, 2380, 4488, 8024, 11441, 48620, 43759, 31842, 18717, 9384, 6120, 9384, 18717, 31842, 43759

Offset: 0

Peter Luschny, Jan 16 2025

			  [0] [    1]
  [1] [    2,     2]
  [2] [    6,     5,     5]
  [3] [   20,    16,    12,    16]
  [4] [   70,    57,    36,    36,   57]
  [5] [  252,   211,   130,    90,  130,  211]
  [6] [  924,   793,   507,   286,  286,  507,  793]
  [7] [ 3432,  3004,  2016,  1092,  728, 1092, 2016,  3004]
  [8] [12870, 11441,  8024,  4488, 2380, 2380, 4488,  8024, 11441]
  [9] [48620, 43759, 31842, 18717, 9384, 6120, 9384, 18717, 31842, 43759]
.
For n = 3 we get the walks depending on the x-coordinate of the endpoint:
W(x= 3) = {WWW},
W(x= 2) = {NWW,WWN,WNW,SWW,WSW,WWS},
W(x= 1) = {NNW,NWN,WNN,NSW,NWS,SWN,SNW,WWE,WEW,EWW,WNS,WSN,SWS,SSW,WSS},
W(x= 0) = {NNN,NNS,NSN,NWE,NEW,SNN,EWN,WNE,WEN,ENW,SNS,SSN,SWE,SEW,WSE,WES,ESW,EWS,NSS,SSS},
W(x=-1) = {NNE,ENN,NEN,NSE,NES,SNE,SEN,WEE,ENS,ESN,EWE,EEW,SSE,SES,ESS},
W(x=-2) = {NEE,SEE,ENE,ESE,EEN,EES},
W(x=-3) = {EEE}.
T(3, 0) = card(W(x=0)) = 20, T(3, 1) = card(W(x=1)) + card(W(x=-3)) = 16,
T(3, 2) = card(W(x=2)) + card(W(x=-2)) = 12, T(3, 3) = card(W(x=3)) + card(W(x=-1)) = 16.

Paolo Xausa, Table of n, a(n) for n = 0..11475 (rows 0..150 of triangle, flattened).
Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Séminaire de Combinatoire Philippe Flajolet, Institut Henri Poincaré, March 28, 2013.
Alin Bostan and Manuel Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008-2009; Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AK, (FPSAC 2009).
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

Related triangles: A052174 (first quadrant), A378067 (upper plane), this triangle (whole plane).

Cf. A000984 (column 0), A323229 (column 1 and main diagonal), A000302 (row sums), A068551 (row sum without column 0), A283799 (row minimum).

T := (n, k) -> binomial(2*n, n - k) + binomial(2*n, k - 1):
seq(print(seq(T(n, k), k = 0..n)), n = 0..9);

A379822[n_, k_] := Binomial[2*n, n - k] + Binomial[2*n, k - 1];
Table[A379822[n, k], {n, 0, 10}, {k, 0, n}] (* Paolo Xausa, May 29 2025 *)

from dataclasses import dataclass
@dataclass
class Walk:
    s: str = ""
    x: int = 0
    y: int = 0
def Trow(n: int) -> list[int]:
    W = [Walk()]
    row = [0] * (n + 1)
    for w in W:
        if len(w.s) == n:
            row[w.x] += 1
        else:
            for s in "NSWE":
                x = y = 0
                match s:
                    case "W": x =  1
                    case "E": x = -1
                    case "N": y =  1
                    case "S": y = -1
                    case _  : pass
                W.append(Walk(w.s + s, w.x + x, w.y + y))
    return row
for n in range(10): print(Trow(n))

T(n, k) = binomial(2*n, n - k) + binomial(2*n, k - 1).

Sum_{k=1..n} T(n, k) = A068551(n).

A378067 Triangle read by rows: T(n, k) is the number of walks of length n with unit steps in all four directions (NSWE) starting at (0, 0), staying in the upper plane (y >= 0), and ending on the vertical line x = 0 if k = 0, or on the line x = k or x = -(n + 1 - k) if k > 0.

Original entry on oeis.org

1, 1, 2, 4, 3, 3, 9, 10, 6, 10, 36, 25, 20, 20, 25, 100, 101, 55, 50, 55, 101, 400, 301, 231, 126, 126, 231, 301, 1225, 1226, 742, 490, 294, 490, 742, 1226, 4900, 3921, 3144, 1632, 1008, 1008, 1632, 3144, 3921, 15876, 15877, 10593, 7137, 3348, 2592, 3348, 7137, 10593, 15877

Offset: 0

Peter Luschny, Dec 08 2024

			Triangle starts:
  [0] [    1]
  [1] [    1,     2]
  [2] [    4,     3,     3]
  [3] [    9,    10,     6,   10]
  [4] [   36,    25,    20,   20,   25]
  [5] [  100,   101,    55,   50,   55,  101]
  [6] [  400,   301,   231,  126,  126,  231,  301]
  [7] [ 1225,  1226,   742,  490,  294,  490,  742, 1226]
  [8] [ 4900,  3921,  3144, 1632, 1008, 1008, 1632, 3144,  3921]
  [9] [15876, 15877, 10593, 7137, 3348, 2592, 3348, 7137, 10593, 15877]
.
For n = 3 we get the walks depending on the x-coordinate of the endpoint:
W(x= 3) = {WWW},
W(x= 2) = {NWW,WNW,WWN},
W(x= 1) = {NNW,NSW,NWN,NWS,WWE,WEW,EWW,WNN,WNS},
W(x= 0) = {NNN,NNS,NSN,NWE,NEW,WNE,WEN,ENW,EWN},
W(x=-1) = {NNE,NEN,ENN,NSE,NES,WEE,ENS,EWE,EEW},
W(x=-2) = {NEE,ENE,EEN},
W(x=-3) = {EEE}.
T(3, 0) = card(W(x=0)) = 9, T(3, 1) = card(W(x=1)) + card(W(x=-3)) = 10,
T(3, 2) = card(W(x=2)) + card(W(x=-2)) = 6, T(3, 3) = card(W(x=3)) + card(W(x=-1)) = 10.

Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Séminaire de Combinatoire Philippe Flajolet, Institut Henri Poincaré, March 28, 2013.
Alin Bostan and Manuel Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008-2009; Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AK, (FPSAC 2009).
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

Related triangles: A052174 (first quadrant), this triangle (upper plane), A379822 (whole plane).

Cf. A018224 (column 0), A001700 (row sums), A378069 (row sum without column 0), A380121 (row minimum).

from dataclasses import dataclass
@dataclass
class Walk:
    s: str = ""
    x: int = 0
    y: int = 0
def Trow(n: int) -> list[int]:
    W = [Walk()]
    row = [0] * (n + 1)
    for w in W:
        if len(w.s) == n:
            row[w.x] += 1
        else:
            for s in "NSWE":
                x = y = 0
                match s:
                    case "W": x =  1
                    case "E": x = -1
                    case "N": y =  1
                    case "S": y = -1
                    case _  : pass
                if w.y + y >= 0:
                    W.append(Walk(w.s + s, w.x + x, w.y + y))
    return row
for n in range(10): print(Trow(n))

Sum_{k=1..n} T(n, k) = 2 * A378069(n).

A380120 Triangle read by rows: T(n, k) is the number of walks of length n on the Z X Z grid with unit steps in all four directions (NSWE) starting at (0, 0). k is the absolute value of the x-coordinate of the endpoint of the walk.

Original entry on oeis.org

1, 2, 2, 6, 8, 2, 20, 30, 12, 2, 70, 112, 56, 16, 2, 252, 420, 240, 90, 20, 2, 924, 1584, 990, 440, 132, 24, 2, 3432, 6006, 4004, 2002, 728, 182, 28, 2, 12870, 22880, 16016, 8736, 3640, 1120, 240, 32, 2, 48620, 87516, 63648, 37128, 17136, 6120, 1632, 306, 36, 2

Offset: 0

Peter Luschny, Jan 17 2025

			Triangle starts:
  [0] [    1]
  [1] [    2,     2]
  [2] [    6,     8,     2]
  [3] [   20,    30,    12,     2]
  [4] [   70,   112,    56,    16,     2]
  [5] [  252,   420,   240,    90,    20,    2]
  [6] [  924,  1584,   990,   440,   132,   24,    2]
  [7] [ 3432,  6006,  4004,  2002,   728,  182,   28,   2]
  [8] [12870, 22880, 16016,  8736,  3640, 1120,  240,  32,  2]
  [9] [48620, 87516, 63648, 37128, 17136, 6120, 1632, 306, 36, 2]
.
For n = 0 there is only the empty walk w = '' with start and end point (x=0, y=0).
For n = 3 the walks depending on the x-coordinate of the endpoint are:
W(x= 3) = {WWW},
W(x= 2) = {NWW,SWW,WNW,WSW,WWN,WWS},
W(x= 1) = {NNW,NSW,NWN,NWS,SNW,SSW,SWN,SWS,WNN,WNS,WSN,WSS,WWE,WEW,EWW},
W(x= 0) = {NNN,NNS,NSN,NSS,NWE,NEW,SNN,SNS,SSN,SSS,SWE,SEW,WNE,WSE,WEN,WES,ENW,ESW,EWN,EWS},
W(x=-1) = {NNE,NSE,NEN,NES,SNE,SSE,SEN,SES,WEE,ENN,ENS,ESN,ESS,EWE,EEW},
W(x=-2) = {NEE,SEE,ENE,ESE,EEN,EES},
W(x=-3) = {EEE}.
T(3, 0) = card(W(x=0)) = 20, T(3, 1) = card(W(x=1)) + card(W(x=-1)) = 30,
T(3, 2) = card(W(x=2)) + card(W(x=-2)) = 12, T(3, 3) = card(W(x=3)) + card(W(x=-3)) = 2.

Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Séminaire de Combinatoire Philippe Flajolet, Institut Henri Poincaré, March 28, 2013.
Alin Bostan and Manuel Kauers, Automatic Classification of Restricted Lattice Walks, arXiv:0811.2899 [math.CO], 2008-2009; Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AK, (FPSAC 2009).
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

Related triangles: A052174 (N X N), A378067 (Z X N), A379822 (Z X Z, variant), A380119.

Cf. A000984 (column 0), A162551 (column 1), A006659 (column 2), A000302 (row sums), A068551 (row sum without column 0), A040000 (row minimum).

T := (n, k) -> ifelse(k = 0, binomial(2*n, n - k), 2*binomial(2*n, n - k)):
seq(print(seq(T(n, k), k = 0..n)), n = 0..9);

from dataclasses import dataclass
@dataclass
class Walk:
    s: str = ""
    x: int = 0
    y: int = 0
def Trow(n: int) -> list[int]:
    W = [Walk()]
    row = [0] * (n + 1)
    for w in W:
        if len(w.s) == n:
            row[abs(w.x)] += 1
        else:
            for s in "NSWE":
                x = y = 0
                match s:
                    case "W": x =  1
                    case "E": x = -1
                    case "N": y =  1
                    case "S": y = -1
                    case _  : pass
                W.append(Walk(w.s + s, w.x + x, w.y + y))
    return row
for n in range(10): print(Trow(n))

T(n, k) = binomial(2*n, n - k) if k = 0, otherwise 2*binomial(2*n, n - k).
Assuming the columns starting at n = 0, i.e. prepended by k zeros:
T(n, k) = [x^n] (2^(2*k+1)*x^k / (sqrt(1-4*x)*(1+sqrt(1-4*x))^(2*k))) for k >= 1.
T(n, k) = n! * [x^n] (2*BesselI(k, 2*x)*exp(2*x)) for k >= 1.

cp's OEIS Frontend

A005560 Number of walks on square lattice. Column y=2 of A052174.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A005559 Number of walks on square lattice. Column y=1 of A052174.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A005561 Number of walks on square lattice. Column y=3 of A052174.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A005562 Number of walks on square lattice. Column y=4 of A052174.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

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

A093768 Positive first differences of the rows of triangle A088459, which enumerates symmetric Dyck paths.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI