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
Examples
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)
Links
- 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.
Crossrefs
Programs
-
Maple
# 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 -
Mathematica
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 *) -
PARI
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
Formula
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.
Comments