A094718 -id:A094718 - cp's OEIS frontend

A080934 Square array read by antidiagonals of number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2n steps with all values less than or equal to k.

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 4, 1, 0, 1, 1, 2, 5, 8, 1, 0, 1, 1, 2, 5, 13, 16, 1, 0, 1, 1, 2, 5, 14, 34, 32, 1, 0, 1, 1, 2, 5, 14, 41, 89, 64, 1, 0, 1, 1, 2, 5, 14, 42, 122, 233, 128, 1, 0, 1, 1, 2, 5, 14, 42, 131, 365, 610, 256, 1, 0, 1, 1, 2, 5, 14, 42, 132, 417, 1094, 1597, 512, 1, 0

Offset: 0

Henry Bottomley, Feb 25 2003

Number of permutations in S_n avoiding both 132 and 123...k.
T(n,k) = number of rooted ordered trees on n nodes of depth <= k. Also, T(n,k) = number of {1,-1} sequences of length 2n summing to 0 with all partial sums are >=0 and <= k. Also, T(n,k) = number of closed walks of length 2n on a path of k nodes starting from (and ending at) a node of degree 1. - Mitch Harris, Mar 06 2004
Also T(n,k) = k-th coefficient in expansion of the rational function R(n), where R(1) = 1, R(n+1) = 1/(1-x*R(n)), which means also that lim(n->inf,R(n)) = g.f. of Catalan numbers (A000108) wherever it has real value (see Mansour article). - Clark Kimberling and Ralf Stephan, May 26 2004
Row n of the array gives Taylor series expansion of F_n(t)/F_{n+1}(t), where F_n(t) are the Fibonacci polynomials defined in A259475 [Kreweras, 1970]. - N. J. A. Sloane, Jul 03 2015

			T(3,2) = 4 since the paths of length 2*3 (7 points) with all values less than or equal to 2 can take the routes 0101010, 0101210, 0121010 or 0121210, but not 0123210.
From _Peter Luschny_, Aug 27 2014: (Start)
Trees with n nodes and height <= h:
h\n  1  2  3  4   5   6    7    8     9    10     11
---------------------------------------------------------
[ 1] 1, 0, 0, 0,  0,  0,   0,   0,    0,    0,     0, ...  A063524
[ 2] 1, 1, 1, 1,  1,  1,   1,   1,    1,    1,     1, ...  A000012
[ 3] 1, 1, 2, 4,  8, 16,  32,  64,  128,  256,   512, ...  A011782
[ 4] 1, 1, 2, 5, 13, 34,  89, 233,  610, 1597,  4181, ...  A001519
[ 5] 1, 1, 2, 5, 14, 41, 122, 365, 1094, 3281,  9842, ...  A124302
[ 6] 1, 1, 2, 5, 14, 42, 131, 417, 1341, 4334, 14041, ...  A080937
[ 7] 1, 1, 2, 5, 14, 42, 132, 428, 1416, 4744, 16016, ...  A024175
[ 8] 1, 1, 2, 5, 14, 42, 132, 429, 1429, 4846, 16645, ...  A080938
[ 9] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4861, 16778, ...  A033191
[10] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16795, ...  A211216
---------------------------------------------------------
The generating functions are listed in A211216. Note that the values up to the main diagonal are the Catalan numbers A000108.
(End)

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Kassie Archer, Ethan Borsh, Jensen Bridges, Christina Graves, and Millie Jeske, Pattern-restricted cyclic permutations with a pattern-restricted cycle form, arXiv:2408.15000 [math.CO], 2024. See also Enum. Comb. Appl. (2025) Vol. 5, No. 1, Art. No. S2R3. See p. 7.
Nicolaas Govert de Bruijn, Donald E. Knuth, and Stephen O. Rice, The Average Height of Planted Plane Trees, Graph Theory and Computing, (1972) 15-22.
Yann Dijoux, Chebyshev polynomials involved in the Householder's method for square roots, arXiv:2501.04703 [math.GM], 2024. Mentions this sequence.
Andrzej Dudek, Jarosław Grytczuk, and Andrzej Ruciński, Largest bipartite sub-matchings of a random ordered matching or a problem with socks, arXiv:2402.02223 [math.CO], 2024.
Nickolas Hein and Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.
Aleksandar Ilic and Andreja Ilic, On the number of restricted Dyck paths, Filomat 25:3 (2011), 191-201; DOI: 10.2298/FIL1103191I.
Anthony Joseph and Polyxeni Lamprou, A new interpretation of Catalan numbers, arXiv preprint arXiv:1512.00406 [math.CO], 2015.
Myrto Kallipoliti, Robin Sulzgruber, and Eleni Tzanaki, Patterns in Shi tableaux and Dyck paths, arXiv:2006.06949 [math.CO], 2020.
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243v1 [math.CO], 2012 (page 10, Corollary 3).
Christian Krattenthaler, Permutations with restricted patterns and Dyck paths, arXiv:math/0002200 [math.CO], 2000.
Germain Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41. See page 38.
Germain Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
Erkko Lehtonen and Tamás Waldhauser, Associative spectra of graph algebras I. Foundations, undirected graphs, antiassociative graphs, arXiv:2011.07621 [math.CO], 2020. See also J. of Algebraic Combinatorics (2021) Vol. 53, 613-638.
Toufik Mansour, Restricted even permutations and Chebyshev polynomials, arXiv:math/0302014 [math.CO], 2003.
Toufik Mansour and Alek Vainshtein, Restricted permutations, continued fractions and Chebyshev polynomials, arXiv:math/9912052 [math.CO], 1999-2000.
Dimana Miroslavova Pramatarova, Investigating the Periodicity of Weighted Catalan Numbers and Generalizing Them to Higher Dimensions, MIT Res. Sci. Instit. (2025). See pp. 5-6.
Thomas Tunstall, Tim Rogers, and Wolfram Möbius, Assisted percolation of slow-spreading mutants in heterogeneous environments, arXiv:2303.01579 [q-bio.PE], 2023.
Vince White, Enumeration of Lattice Paths with Restrictions, (2024). Electronic Theses and Dissertations. 2799. See pp. 20, 25.

Cf. A000108, A079214, A080935, A080936. Rows include A000012, A057427, A040000 (offset), columns include (essentially) A000007, A000012, A011782, A001519, A007051, A080937, A024175, A080938, A033191, A211216. Main diagonal is A000108.

Cf. A094718 (involutions). Cf. also A259475.

# As a triangular array:
b:= proc(x, y, k) option remember; `if`(y>min(k, x) or y<0, 0,
      `if`(x=0, 1, b(x-1, y-1, k)+ b(x-1, y+1, k)))
    end:
A:= (n, k)-> b(2*n, 0, k):
seq(seq(A(n, d-n), n=0..d), d=0..12);  # Alois P. Heinz, Aug 06 2012
# As a square array:
A := proc(n,k) option remember; local j; if n = 1 then 1 elif k = 1 then 0 else add(A(n-j,k)*A(j,k-1), j=1..n-1) fi end:
linalg[matrix](10, 12, (n,k) -> A(k,n)); # Peter Luschny, Aug 27 2014

A[n_, k_] := A[n, k] = Which[n == 1, 1, k == 1, 0, True, Sum[A[n-j, k]*A[j, k-1], {j, 1, n-1}]]; Table[A[k-n+1, n], {k, 1, 13}, {n, k, 1, -1}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Peter Luschny *)

A(N, K) = {
  my(m = matrix(N, K, n, k, n==1));
  for (n = 2, N,
  for (k = 2, K,
       m[n,k] = sum(i = 1, n-1, m[n-i,k] * m[i,k-1])));
  return(m);
}
A(11,10)~  \\ Gheorghe Coserea, Jan 13 2016

T(n, k) = Sum_{0A080935(n, k) = T(n, k-1)+A080936(n, k); for k>=n T(n, k) = A000108(n).
T(n, k) = 2^(2n+1)/(k+2) * Sum_{i=1..k+1} (sin(Pi*i/(k+2))*cos(Pi*i/(k+2))^n)^2 for n>=1. - Herbert Kociemba, Apr 28 2004
G.f. of n-th row: B(n)/B(n+1) where B(j)=[(1+sqrt(1-4x))/2]^j-[(1-sqrt(1-4x))/2]^j.

A068914 Square array read by antidiagonals of number of k step walks (each step +-1 starting from 0) which are never more than n or less than 0.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 2, 2, 1, 1, 0, 1, 4, 3, 2, 1, 1, 0, 1, 4, 5, 3, 2, 1, 1, 0, 1, 8, 8, 6, 3, 2, 1, 1, 0, 1, 8, 13, 9, 6, 3, 2, 1, 1, 0, 1, 16, 21, 18, 10, 6, 3, 2, 1, 1, 0, 1, 16, 34, 27, 19, 10, 6, 3, 2, 1, 1, 0, 1, 32, 55, 54, 33, 20, 10, 6, 3, 2, 1, 1, 0, 1, 32, 89

Offset: 0

Henry Bottomley, Mar 06 2002

The (n,k)-entry of the square array is p(n,k) in the R. Kemp reference (see Table 1 on p. 160 and Theorem 2 on p. 159). - Emeric Deutsch, Jun 16 2011

			Rows start:
1,0,0,0,0,...;
1,1,1,1,1,...;
1,1,2,2,4,...;
1,1,2,3,5,...;
etc.

Stefano Spezia, First 151 antidiagonals of the array, flattened
Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015. See formula 0.2, p. 2.
Nancy S. S. Gu, Helmut Prodinger, Combinatorics on lattice paths in strips, arXiv:2004.00684 [math.CO], 2020. See p. 2.
R. Kemp, On the average depth of a prefix of the Dycklanguage D_1, Discrete Math., 36, 1981, 155-170.

Rows include effectively A000007, A000012, A016116, A000045, A038754, A028495, A030436, A061551. Central and lower diagonals are A001405. Cf. A068913 for starting in the middle rather than an edge.

Reflected version of A094718.

v := ((1-sqrt(1-4*z^2))*1/2)/z: G := proc (k) options operator, arrow: (1+v^2)*(1-v^(k+1))/((1-v)*(1+v^(k+2))) end proc: a := proc (n, k) options operator, arrow: coeff(series(G(k), z = 0, 80), z, n) end proc: for n from 0 to 15 do seq(a(n, k), k = 0 .. 15) end do; # yields the first 16 entries of the first 16 rows of the square array
v := ((1-sqrt(1-4*z^2))*1/2)/z: G := proc (k) options operator, arrow: (1+v^2)*(1-v^(k+1))/((1-v)*(1+v^(k+2))) end proc: a := proc (n, k) options operator, arrow: coeff(series(G(k), z = 0, 80), z, n) end proc: for n from 0 to 13 do seq(a(n-i, i), i = 0 .. n) end do; # yields the first 14 antidiagonals of the square array in triangular form

v = (1-Sqrt[1-4z^2])/(2z); f[k_] = (1+v^2)*(1-v^(k+1))/((1-v)*(1+v^(k+2))) ; m = 14; a = Table[ PadRight[ CoefficientList[ Series[f[k], {z, 0, m}], z], m], {k, 0, m}]; Flatten[Table[a[[n+1-k, k]], {n, m}, {k, n, 1, -1}]][[;; 95]] (* Jean-François Alcover, Jul 13 2011, after Emeric Deutsch *)

T(n,k) = sum(j=floor(-n/(k+2)), ceil(n/(k+2)), (-1)^j*binomial(n,floor((n+(k+2)*j)/2))); \\ Stefano Spezia, May 08 2020

An explicit expression for the (n,k)-entry of the square array can be found in the R. Kemp reference (Theorem 2 on p. 159). - Emeric Deutsch, Jun 16 2011

The g.f. of column k is (1 + v^2)*(1 - v^(k+1))/((1 - v)*(1 + v^(k+2))), where v = (1 - sqrt(1-4*z^2))/(2*z) (see p. 159 of the R. Kemp reference). - Emeric Deutsch, Jun 16 2011

A336675 Number of paths of length n starting at initial node of the path graph P_10.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 251, 460, 911, 1690, 3327, 6225, 12190, 22950, 44744, 84626, 164407, 312019, 604487, 1150208, 2223504, 4239225, 8181175, 15621426, 30108147, 57556155, 110820165, 212037241, 407946421, 781074572, 1501844193, 2877011660, 5529362694

Offset: 0

Nachum Dershowitz, Jul 30 2020

Also the number of paths along a corridor width 10, starting from one side.

In general, a(n,m) = (2^n/(m+1))*Sum_{r=1..m} (1-(-1)^r)*cos(Pi*r/(m+1))^n*(1+cos(Pi*r/(m+1))) gives the number of paths of length n starting at the initial node on the path graph P_m. Here we have m=10. - Herbert Kociemba, Sep 14 2020

Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015-2016.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
Index entries for linear recurrences with constant coefficients, signature (1,4,-3,-3,1).

This is row 10 of A094718. Bisections give A224514 (even part), A216710 (odd part).

Cf. A000004 (row 0), A000007 (row 1), A000012 (row 2), A016116 (row 3), A000045 (row 4), A038754 (row 5), A028495 (row 6), A030436 (row 7), A061551 (row 8), A178381 (row 9), this sequence (row 10), A336678 (row 11), A001405 (limit).

X := j -> (-1)^(j/11) - (-1)^(1-j/11):
a := k -> add((2 + X(j))*X(j)^k, j in [1, 3, 5, 7, 9])/11:
seq(simplify(a(n)), n=0..30); # Peter Luschny, Sep 17 2020

a[n_,m_]:=2^(n+1)/(m+1) Module[{x=(Pi r)/(m+1)},Sum[Cos[x]^n (1+Cos[x]),{r,1,m,2}]]
Table[a[n,10],{n,0,40}]//Round (* Herbert Kociemba, Sep 14 2020 *)

my(x='x+O('x^44)); Vec((1 - 3*x^2 + x^4)/(1 - x - 4*x^2 + 3*x^3 + 3*x^4 - x^5)) \\ Joerg Arndt, Jul 31 2020

From Stefano Spezia, Jul 30 2020: (Start)
G.f.: (1 - 3*x^2 + x^4)/(1 - x - 4*x^2 + 3*x^3 + 3*x^4 - x^5).
a(n) = a(n-1) + 4*a(n-2) - 3*a(n-3) - 3*a(n-4) + a(n-5) for n > 4. (End)
a(n) = (2^n/11)*Sum_{r=1..10} (1-(-1)^r)*cos(Pi*r/11)^n*(1+cos(Pi*r/11)). - Herbert Kociemba, Sep 14 2020

A336678 Number of paths of length n starting at initial node of the path graph P_11.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 461, 922, 1702, 3404, 6315, 12630, 23494, 46988, 87533, 175066, 326382, 652764, 1217483, 2434966, 4542526, 9085052, 16950573, 33901146, 63255670, 126511340, 236063915, 472127830, 880983606, 1761967212, 3287837741

Offset: 0

Nachum Dershowitz, Jul 30 2020

Also the number of paths along a corridor width 11, starting from one side.

Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015-2016.
Nachum Dershowitz, Between Broadway and the Hudson: A Bijection of Corridor Paths, arXiv:2006.06516 [math.CO], 2020.
Index entries for linear recurrences with constant coefficients, signature (0,6,0,-9,0,2).

This is row 11 of A094718. Bisections give A087944 (even part), A087946 (odd part).
Cf. A000004 (row 0), A000007 (row 1), A000012 (row 2), A016116 (row 3), A000045 (row 4), A038754 (row 5), A028495 (row 6), A030436 (row 7), A061551 (row 8),
A178381 (row 9), A336675 (row 10), this sequence (row 11), A001405 (limit).

X := j -> (-1)^(j/12) - (-1)^(1-j/12):
a := k -> add((2 + X(j))*X(j)^k, j in [1, 3, 5, 7, 9, 11])/12:
seq(simplify(a(n)), n=0..30); # Peter Luschny, Sep 17 2020

LinearRecurrence[{0, 6, 0, -9, 0, 2}, {1, 1, 2, 3, 6, 10}, 40] (* Harvey P. Dale, Sep 08 2020 *)
a[n_,m_]:=2^(n+1)/(m+1) Module[{x=(Pi r)/(m+1)},Sum[Cos[x]^n (1+Cos[x]),{r,1,m,2}]]
Table[a[n,11], {n,0,40}]//Round (* Herbert Kociemba, Sep 14 2020 *)

my(x='x+O('x^44)); Vec(-(x^5+3*x^4-3*x^3-4*x^2+x+1)/((2*x^2-1)*(x^4-4*x^2+1))) \\ Joerg Arndt, Jul 31 2020

G.f.: -(x^5+3*x^4-3*x^3-4*x^2+x+1)/((2*x^2-1)*(x^4-4*x^2+1)).

a(n) = (2^n/12)*Sum_{r=1..11} (1-(-1)^r)*cos(Pi*r/12)^n*(1+cos(Pi*r/12)). - Herbert Kociemba, Sep 14 2020

cp's OEIS Frontend

A080934 Square array read by antidiagonals of number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2n steps with all values less than or equal to k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A068914 Square array read by antidiagonals of number of k step walks (each step +-1 starting from 0) which are never more than n or less than 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A336675 Number of paths of length n starting at initial node of the path graph P_10.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A336678 Number of paths of length n starting at initial node of the path graph P_11.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula