OFFSET
0,13
COMMENTS
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
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.
N. G. de Bruijn, D. E. Knuth, and S. 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.
A. Joseph and P. 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).
C. Krattenthaler, Permutations with restricted patterns and Dyck paths, arXiv:math/0002200 [math.CO], 2000.
G. 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.
G. 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.
T. Mansour, Restricted even permutations and Chebyshev polynomials, arXiv:math/0302014 [math.CO], 2003.
T. Mansour and A. Vainshtein, Restricted permutations, continued fractions and Chebyshev polynomials, arXiv:math/9912052 [math.CO], 1999-2000.
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.
FORMULA
T(n, k) = Sum_{0<i<n} T(i, k)*T(n-i, k-1) with T(0, k) = 1 and T(n, 0) = 0^n. For 1<=k<=n T(n, k) = A080935(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.
EXAMPLE
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)
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Henry Bottomley, Feb 25 2003
STATUS
approved