A283799 -id:A283799 - cp's OEIS frontend

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.

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

A282869 Triangle read by rows: T(n,k) is the number of dispersed Dyck prefixes (i.e., left factors of Motzkin paths with no (1,0) steps at positive heights) of length n and height k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 7, 5, 2, 1, 1, 12, 10, 6, 2, 1, 1, 20, 21, 12, 7, 2, 1, 1, 33, 41, 28, 14, 8, 2, 1, 1, 54, 81, 56, 36, 16, 9, 2, 1, 1, 88, 155, 120, 72, 45, 18, 10, 2, 1, 1, 143, 297, 239, 165, 90, 55, 20, 11, 2, 1, 1, 232, 560, 492, 330, 220, 110, 66, 22, 12, 2, 1, 1, 376, 1054, 974, 715, 440, 286, 132, 78, 24, 13, 2, 1

Offset: 0

Steven Finch, Feb 23 2017

Row n has n+1 entries.

			Triangle starts:
  1;
  1,  1;
  1,  2,  1;
  1,  4,  2,  1;
  1,  7,  5,  2, 1;
  1, 12, 10,  6, 2, 1;
  1, 20, 21, 12, 7, 2, 1;
  ...
T(4,3) = 2 because we have UUUD and HUUU, where U=(1,1), D=(1,-1), H=(1,0).
T(4,2) = 5 because we have UUDD, UUDU, UDUU, HUUD and HHUU.

Alois P. Heinz, Rows n = 0..140, flattened
Steven R. Finch, How far might we walk at random?, arXiv:1802.04615 [math.HO], 2018.

Row sums give A000079.
T(2n,n) gives A283799.
Cf. A000071, A191314.

b:= proc(x, y, m) option remember;
      `if`(x=0, z^m, `if`(y>0, b(x-1, y-1, m), 0)+
      `if`(y=0, b(x-1, y, m), 0)+b(x-1, y+1, max(m, y+1)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(n, 0$2)):
seq(T(n), n=0..16);  # Alois P. Heinz, Mar 13 2017

b[x_, y_, m_] := b[x, y, m] = If[x == 0, z^m, If[y > 0, b[x - 1, y - 1, m], 0] + If[y == 0, b[x - 1, y, m], 0] + b[x - 1, y + 1, Max[m, y + 1]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][ b[n, 0, 0]];
Table[T[n], {n, 0, 16}] // Flatten (* Jean-François Alcover, May 12 2017, after Alois P. Heinz *)

T(n,1) = A000071(n+1), (Fibonacci numbers minus 1).

A283667 Number of Motzkin prefixes of length 2n and height n.

Original entry on oeis.org

1, 3, 13, 64, 334, 1802, 9933, 55575, 314362, 1793126, 10295625, 59430043, 344559826, 2005026610, 11703965955, 68503652100, 401892122682, 2362629703214, 13914547415998, 82081163986020, 484893156220356, 2868234297838092, 16986185485228431, 100703275233924096

Offset: 0

Alois P. Heinz, Mar 13 2017

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1279

Cf. A283595, A283799.

a:= proc(n) option remember; `if`(n<2, 1+2*n, ((4*n-2)*(455*n^6-
       1155*n^5-2776*n^4+1047*n^3+1493*n^2-72*n-72)*a(n-1)+36*
      (n-1)*(2*n-1)*(2*n-3)*(13*n^4-7*n^3-64*n^2-44*n-6)*a(n-2))/
      ((9*n+6)*(3*n+1)*(n+1)*(13*n^4-59*n^3+35*n^2+11*n-6)))
    end:
seq(a(n), n=0..30);

b[x_, y_, m_] := b[x, y, m] = If[x == 0, z^m, b[x - 1, y, m] + If[y > 0, b[x - 1, y - 1, m], 0] + b[x - 1, y + 1, Max[m, y + 1]]];
a[n_] := SeriesCoefficient[b[2n, 0, 0], {z, 0, n}];
a /@ Range[0, 30] (* Jean-François Alcover, May 11 2020, after Alois P. Heinz in A283595 *)

Recursion: see Maple program.
a(n) = A283595(2n,n).
a(n) ~ sqrt(769 + 2762/sqrt(13)) * (70 + 2*13^(3/2))^n / (3^(3*n+3)*sqrt(3*Pi*n)). - Vaclav Kotesovec, Mar 13 2017

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A282869 Triangle read by rows: T(n,k) is the number of dispersed Dyck prefixes (i.e., left factors of Motzkin paths with no (1,0) steps at positive heights) of length n and height k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A283667 Number of Motzkin prefixes of length 2n and height n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula