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.

%I A080934 #114 Aug 27 2025 11:40:25
%S A080934 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 A080934 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 A080934 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 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.
%C A080934 Number of permutations in S_n avoiding both 132 and 123...k.
%C A080934 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 A080934 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 A080934 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 A080934 Alois P. Heinz, <a href="/A080934/b080934.txt">Antidiagonals n = 0..140, flattened</a>
%H A080934 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 A080934 Nicolaas Govert de Bruijn, Donald E. Knuth, and Stephen 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 A080934 Yann Dijoux, <a href="https://arxiv.org/abs/2501.04703">Chebyshev polynomials involved in the Householder's method for square roots</a>, arXiv:2501.04703 [math.GM], 2024. Mentions this sequence.
%H A080934 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 A080934 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 A080934 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 A080934 Anthony Joseph and Polyxeni 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 A080934 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 A080934 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 A080934 Christian Krattenthaler, <a href="https://arxiv.org/abs/math/0002200">Permutations with restricted patterns and Dyck paths</a>, arXiv:math/0002200 [math.CO], 2000.
%H A080934 Germain  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 A080934 Germain 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 A080934 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 A080934 Toufik Mansour, <a href="https://arxiv.org/abs/math/0302014">Restricted even permutations and Chebyshev polynomials</a>, arXiv:math/0302014 [math.CO], 2003.
%H A080934 Toufik Mansour and Alek 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 A080934 Dimana Miroslavova Pramatarova, <a href="https://www.cee.org/sites/default/files/rsi/Papers/pramatarovadimana_193982_5452885_Pramatarova_Dimana_AnaMaria_Final.pdf">Investigating the Periodicity of Weighted Catalan Numbers and Generalizing Them to Higher Dimensions</a>, MIT Res. Sci. Instit. (2025). See pp. 5-6.
%H A080934 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 A080934 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 A080934 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 A080934 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 A080934 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 A080934 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 A080934 From _Peter Luschny_, Aug 27 2014: (Start)
%e A080934 Trees with n nodes and height <= h:
%e A080934 h\n  1  2  3  4   5   6    7    8     9    10     11
%e A080934 ---------------------------------------------------------
%e A080934 [ 1] 1, 0, 0, 0,  0,  0,   0,   0,    0,    0,     0, ...  A063524
%e A080934 [ 2] 1, 1, 1, 1,  1,  1,   1,   1,    1,    1,     1, ...  A000012
%e A080934 [ 3] 1, 1, 2, 4,  8, 16,  32,  64,  128,  256,   512, ...  A011782
%e A080934 [ 4] 1, 1, 2, 5, 13, 34,  89, 233,  610, 1597,  4181, ...  A001519
%e A080934 [ 5] 1, 1, 2, 5, 14, 41, 122, 365, 1094, 3281,  9842, ...  A124302
%e A080934 [ 6] 1, 1, 2, 5, 14, 42, 131, 417, 1341, 4334, 14041, ...  A080937
%e A080934 [ 7] 1, 1, 2, 5, 14, 42, 132, 428, 1416, 4744, 16016, ...  A024175
%e A080934 [ 8] 1, 1, 2, 5, 14, 42, 132, 429, 1429, 4846, 16645, ...  A080938
%e A080934 [ 9] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4861, 16778, ...  A033191
%e A080934 [10] 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16795, ...  A211216
%e A080934 ---------------------------------------------------------
%e A080934 The generating functions are listed in A211216. Note that the values up to the main diagonal are the Catalan numbers A000108.
%e A080934 (End)
%p A080934 # As a triangular array:
%p A080934 b:= proc(x, y, k) option remember; `if`(y>min(k, x) or y<0, 0,
%p A080934       `if`(x=0, 1, b(x-1, y-1, k)+ b(x-1, y+1, k)))
%p A080934     end:
%p A080934 A:= (n, k)-> b(2*n, 0, k):
%p A080934 seq(seq(A(n, d-n), n=0..d), d=0..12);  # _Alois P. Heinz_, Aug 06 2012
%p A080934 # As a square array:
%p A080934 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 A080934 linalg[matrix](10, 12, (n,k) -> A(k,n)); # _Peter Luschny_, Aug 27 2014
%t A080934 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 A080934 (PARI)
%o A080934 A(N, K) = {
%o A080934   my(m = matrix(N, K, n, k, n==1));
%o A080934   for (n = 2, N,
%o A080934   for (k = 2, K,
%o A080934        m[n,k] = sum(i = 1, n-1, m[n-i,k] * m[i,k-1])));
%o A080934   return(m);
%o A080934 }
%o A080934 A(11,10)~  \\ _Gheorghe Coserea_, Jan 13 2016
%Y A080934 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 A080934 Cf. A094718 (involutions). Cf. also A259475.
%K A080934 nonn,tabl,changed
%O A080934 0,13
%A A080934 _Henry Bottomley_, Feb 25 2003