%I #107 Oct 24 2024 09:25:30
%S 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,
%T 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,
%U 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
%N 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.
%C Number of permutations in S_n avoiding both 132 and 123...k.
%C 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
%C 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
%C 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
%H Alois P. Heinz, <a href="/A080934/b080934.txt">Antidiagonals n = 0..140, flattened</a>
%H Kassie Archer, Ethan Borsh, Jensen Bridges, Christina Graves, and Millie Jeske, <a href="https://arxiv.org/abs/2408.15000">Pattern-restricted cyclic permutations with a pattern-restricted cycle form</a>, arXiv:2408.15000 [math.CO], 2024. See also <a href="https://doi.org/10.54550/ECA2025V5S1R3">Enum. Comb. Appl.</a> (2025) Vol. 5, No. 1, Art. No. S2R3. See p. 7.
%H N. G. de Bruijn, D. E. Knuth, and S. O. Rice, <a href="http://alexandria.tue.nl/repository/freearticles/597601.pdf">The Average Height of Planted Plane Trees</a>, Graph Theory and Computing, (1972) 15-22.
%H Andrzej Dudek, Jarosław Grytczuk, and Andrzej Ruciński, <a href="https://arxiv.org/abs/2402.02223">Largest bipartite sub-matchings of a random ordered matching or a problem with socks</a>, arXiv:2402.02223 [math.CO], 2024.
%H Nickolas Hein and Jia Huang, <a href="https://arxiv.org/abs/1807.04623">Variations of the Catalan numbers from some nonassociative binary operations</a>, arXiv:1807.04623 [math.CO], 2018.
%H Aleksandar Ilic and Andreja Ilic, <a href="http://dx.doi.org/10.2298/FIL1103191I">On the number of restricted Dyck paths</a>, Filomat 25:3 (2011), 191-201; DOI: 10.2298/FIL1103191I.
%H A. Joseph and P. Lamprou, <a href="http://arxiv.org/abs/1512.00406">A new interpretation of Catalan numbers</a>, arXiv preprint arXiv:1512.00406 [math.CO], 2015.
%H Myrto Kallipoliti, Robin Sulzgruber, and Eleni Tzanaki, <a href="https://arxiv.org/abs/2006.06949">Patterns in Shi tableaux and Dyck paths</a>, arXiv:2006.06949 [math.CO], 2020.
%H Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, <a href="http://arxiv.org/abs/1201.6243">Marked mesh patterns in 132-avoiding permutations I,</a> arXiv:1201.6243v1 [math.CO], 2012 (page 10, Corollary 3).
%H C. Krattenthaler, <a href="https://arxiv.org/abs/math/0002200">Permutations with restricted patterns and Dyck paths</a>, arXiv:math/0002200 [math.CO], 2000.
%H G. Kreweras, <a href="http://www.numdam.org/item?id=BURO_1970__15__3_0">Sur les éventails de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationelle, Cahier no. 15, Paris, 1970, pp. 3-41. See page 38.
%H G. Kreweras, <a href="/A000108/a000108_1.pdf">Sur les éventails de segments</a>, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
%H Erkko Lehtonen and Tamás Waldhauser, <a href="https://arxiv.org/abs/2011.07621">Associative spectra of graph algebras I. Foundations, undirected graphs, antiassociative graphs</a>, arXiv:2011.07621 [math.CO], 2020. See also <a href="https://doi.org/10.1007/s10801-020-01010-w">J. of Algebraic Combinatorics</a> (2021) Vol. 53, 613-638.
%H T. Mansour, <a href="https://arxiv.org/abs/math/0302014">Restricted even permutations and Chebyshev polynomials</a>, arXiv:math/0302014 [math.CO], 2003.
%H T. Mansour and A. Vainshtein, <a href="https://arxiv.org/abs/math/9912052">Restricted permutations, continued fractions and Chebyshev polynomials</a>, arXiv:math/9912052 [math.CO], 1999-2000.
%H Thomas Tunstall, Tim Rogers, and Wolfram Möbius, <a href="https://arxiv.org/abs/2303.01579">Assisted percolation of slow-spreading mutants in heterogeneous environments</a>, arXiv:2303.01579 [q-bio.PE], 2023.
%H Vince White, <a href="https://digitalcommons.georgiasouthern.edu/etd/2799">Enumeration of Lattice Paths with Restrictions</a>, (2024). Electronic Theses and Dissertations. 2799. See pp. 20, 25.
%F 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).
%F 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
%F 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.
%e 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.
%e From _Peter Luschny_, Aug 27 2014: (Start)
%e Trees with n nodes and height <= h:
%e h\n 1 2 3 4 5 6 7 8 9 10 11
%e ---------------------------------------------------------
%e [ 1] 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... A063524
%e [ 2] 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A000012
%e [ 3] 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ... A011782
%e [ 4] 1, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, ... A001519
%e [ 5] 1, 1, 2, 5, 14, 41, 122, 365, 1094, 3281, 9842, ... A124302
%e [ 6] 1, 1, 2, 5, 14, 42, 131, 417, 1341, 4334, 14041, ... A080937
%e [ 7] 1, 1, 2, 5, 14, 42, 132, 428, 1416, 4744, 16016, ... A024175
%e [ 8] 1, 1, 2, 5, 14, 42, 132, 429, 1429, 4846, 16645, ... A080938
%e [ 9] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4861, 16778, ... A033191
%e [10] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16795, ... A211216
%e ---------------------------------------------------------
%e The generating functions are listed in A211216. Note that the values up to the main diagonal are the Catalan numbers A000108.
%e (End)
%p # As a triangular array:
%p b:= proc(x, y, k) option remember; `if`(y>min(k, x) or y<0, 0,
%p `if`(x=0, 1, b(x-1, y-1, k)+ b(x-1, y+1, k)))
%p end:
%p A:= (n, k)-> b(2*n, 0, k):
%p seq(seq(A(n, d-n), n=0..d), d=0..12); # _Alois P. Heinz_, Aug 06 2012
%p # As a square array:
%p 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:
%p linalg[matrix](10, 12, (n,k) -> A(k,n)); # _Peter Luschny_, Aug 27 2014
%t 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_ *)
%o (PARI)
%o A(N, K) = {
%o my(m = matrix(N, K, n, k, n==1));
%o for (n = 2, N,
%o for (k = 2, K,
%o m[n,k] = sum(i = 1, n-1, m[n-i,k] * m[i,k-1])));
%o return(m);
%o }
%o A(11,10)~ \\ _Gheorghe Coserea_, Jan 13 2016
%Y 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.
%Y Cf. A094718 (involutions). Cf. also A259475.
%K nonn,tabl,changed
%O 0,13
%A _Henry Bottomley_, Feb 25 2003