A036766 -id:A036766 - cp's OEIS frontend

A036765 Number of ordered rooted trees with n non-root nodes and all outdegrees <= three.

1, 1, 2, 5, 13, 36, 104, 309, 939, 2905, 9118, 28964, 92940, 300808, 980864, 3219205, 10626023, 35252867, 117485454, 393133485, 1320357501, 4449298136, 15038769672, 50973266380, 173214422068, 589998043276, 2014026871496, 6889055189032, 23608722350440

Offset: 0

N. J. A. Sloane

Number of Dyck n-paths that avoid UUUU. For example, a(4)=13 counts all 14 Dyck 4-paths except UUUUDDDD. - David Callan, Dec 09 2004
Number of restricted growth strings for Dyck paths with at most 2 consecutive rises (this is equivalent to the comment above, see example). - Joerg Arndt, Oct 31 2012
Let A(x) be the g.f. for the sequence of numbers of Dyck words with at most k consecutive ones (paths with at most k consecutive up-steps 'U', Restricted Growth Strings with at most k-1 consecutive rises), then B(x) := x*A(x) is the series reversion of x/(1+x+x^2+...+x^k). - Joerg Arndt, Oct 31 2012
a(n) is the number of ordered unlabeled rooted trees on n+1 nodes where each node has no more than 3 children. - Geoffrey Critzer, Jan 05 2013
a(n) = number of noncrossing partitions of [n] in which all blocks are of size <= 3. - David Callan, Aug 27 2014

			a(4) = 13 since the top row of M^4 = (13, 8, 4, 1, 1).
From _Joerg Arndt_, Oct 31 2012: (Start)
a(5)=36 because there are 36 Dyck words of length 5 that avoid "1111":
[ #]      RGS                rises         Dyck word
[ 1]    [ . . . . . ]     [ . . . . . ]    1.1.1.1.1.
[ 2]    [ . . . . 1 ]     [ . . . . 1 ]    1.1.1.11..
[ 3]    [ . . . 1 . ]     [ . . . 1 . ]    1.1.11..1.
[ 4]    [ . . . 1 1 ]     [ . . . 1 . ]    1.1.11.1..
[ 5]    [ . . . 1 2 ]     [ . . . 1 2 ]    1.1.111...
[ 6]    [ . . 1 . . ]     [ . . 1 . . ]    1.11..1.1.
[ 7]    [ . . 1 . 1 ]     [ . . 1 . 1 ]    1.11..11..
[ 8]    [ . . 1 1 . ]     [ . . 1 . . ]    1.11.1..1.
[ 9]    [ . . 1 1 1 ]     [ . . 1 . . ]    1.11.1.1..
[10]    [ . . 1 1 2 ]     [ . . 1 . 1 ]    1.11.11...
[11]    [ . . 1 2 . ]     [ . . 1 2 . ]    1.111...1.
[12]    [ . . 1 2 1 ]     [ . . 1 2 . ]    1.111..1..
[13]    [ . . 1 2 2 ]     [ . . 1 2 . ]    1.111.1...
[--]    [ . . 1 2 3 ]     [ . . 1 2 3 ]    1.1111....
[14]    [ . 1 . . . ]     [ . 1 . . . ]    11..1.1.1.
[15]    [ . 1 . . 1 ]     [ . 1 . . 1 ]    11..1.11..
[16]    [ . 1 . 1 . ]     [ . 1 . 1 . ]    11..11..1.
[17]    [ . 1 . 1 1 ]     [ . 1 . 1 . ]    11..11.1..
[18]    [ . 1 . 1 2 ]     [ . 1 . 1 2 ]    11..111...
[19]    [ . 1 1 . . ]     [ . 1 . . . ]    11.1..1.1.
[20]    [ . 1 1 . 1 ]     [ . 1 . . 1 ]    11.1..11..
[21]    [ . 1 1 1 . ]     [ . 1 . . . ]    11.1.1..1.
[22]    [ . 1 1 1 1 ]     [ . 1 . . . ]    11.1.1.1..
[23]    [ . 1 1 1 2 ]     [ . 1 . . 1 ]    11.1.11...
[24]    [ . 1 1 2 . ]     [ . 1 . 1 . ]    11.11...1.
[25]    [ . 1 1 2 1 ]     [ . 1 . 1 . ]    11.11..1..
[26]    [ . 1 1 2 2 ]     [ . 1 . 1 . ]    11.11.1...
[27]    [ . 1 1 2 3 ]     [ . 1 . 1 2 ]    11.111....
[28]    [ . 1 2 . . ]     [ . 1 2 . . ]    111...1.1.
[29]    [ . 1 2 . 1 ]     [ . 1 2 . 1 ]    111...11..
[30]    [ . 1 2 1 . ]     [ . 1 2 . . ]    111..1..1.
[31]    [ . 1 2 1 1 ]     [ . 1 2 . . ]    111..1.1..
[32]    [ . 1 2 1 2 ]     [ . 1 2 . 1 ]    111..11...
[33]    [ . 1 2 2 . ]     [ . 1 2 . . ]    111.1...1.
[34]    [ . 1 2 2 1 ]     [ . 1 2 . . ]    111.1..1..
[35]    [ . 1 2 2 2 ]     [ . 1 2 . . ]    111.1.1...
[36]    [ . 1 2 2 3 ]     [ . 1 2 . 1 ]    111.11....
[--]    [ . 1 2 3 . ]     [ . 1 2 3 . ]    1111....1.
[--]    [ . 1 2 3 1 ]     [ . 1 2 3 . ]    1111...1..
[--]    [ . 1 2 3 2 ]     [ . 1 2 3 . ]    1111..1...
[--]    [ . 1 2 3 3 ]     [ . 1 2 3 . ]    1111.1....
[--]    [ . 1 2 3 4 ]     [ . 1 2 3 4 ]    11111.....
(Dots are used for zeros for readability.)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
Paul Barry, d-orthogonal polynomials, Fuss-Catalan matrices and lattice paths, arXiv:2505.16718 [math.CO], 2025. See p. 25.
N. T. Cameron, Random walks, trees and extensions of Riordan group techniques, Dissertation, Howard University, 2002.
Naiomi Cameron and J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, Article #16.6.1.
Colin Defant and Kai Zheng, Stack-Sorting with Consecutive-Pattern-Avoiding Stacks, arXiv:2008.12297 [math.CO], 2020.
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908 [math.CO], 2012.
M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.
Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.
Nickolas Hein and Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015.
Nickolas Hein and Jia Huang, Modular Catalan Numbers, European Journal of Combinatorics 61 (2017), 197-218.
JiSun Huh, Sangwook Kim, Seunghyun Seo, and Heesung Shin, Bijections on pattern avoiding inversion sequences and related objects, arXiv:2404.04091 [math.CO], 2024. See p. 22.
L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012. - From _N. J. A. Sloane_, Jan 03 2013
A. Sapounakis, I. Tasoulas, and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).
M. Wallner, Lattice Path Combinatorics, Diplomarbeit, Institut für Diskrete Mathematik und Geometrie der Technischen Universität Wien, 2013.
Index entries for sequences related to rooted trees

Right hand column of triangle A064580. The sequence of sequences A000007 (0^n), A000012 (constant 1), A001006 (Motzkin), A036765, A036766, ... tends to A000108 (Catalan).
Cf. A005725, A186241, A198951, A200731.
Column k=3 of A288942.

[&+[Binomial(n+1, n-2*k)*Binomial(n+1, k)/(n+1): k in [0..n]]: n in [0..30]]; // Vincenzo Librandi, Oct 16 2018

r := 3; [ seq((1/n)*add( (-1)^j*binomial(n,j)*binomial(2*n-2-j*(r+1), n-1),j=0..floor((n-1)/(r+1))), n=1..30) ];
# second Maple program:
b:= proc(u, o) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1), j=1..min(1, u))+
      add(b(u+j-1, o-j), j=1..min(3, o)))
    end:
a:= n-> b(0, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 28 2017

InverseSeries[Series[y/(1+y+y^2+y^3), {y, 0, 24}], x] (* then A(x)=y(x)/x *) (* Len Smiley, Apr 11 2000 *)
b[u_, o_, k_] := b[u, o, k] = If[u + o == 0, 1, Sum[b[u - j, o + j - 1, k], {j, 1, Min[1, u]}] + Sum[b[u + j - 1, o - j, k], {j, 1, Min[k, o]}]];
a[n_] := b[0, n, 3];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 05 2017, after Alois P. Heinz *)
Table[HypergeometricPFQ[{-n-1, (1-n)/2, -n/2}, {1, 3/2}, -1], {n, 0, 28}] (* Vladimir Reshetnikov, Oct 15 2018 *)

{a(n)=sum(j=0,n\2,binomial(n+1, n-2*j)*binomial(n+1,j))/(n+1)}

{a(n)=local(A=1+x+x*O(x^n));for(i=1,n,A=1+x*A+(x*A)^2+(x*A)^3);polcoeff(A,n)}

{a(n)=local(A=1+x);for(i=1,n,A=exp(sum(m=1, n, sum(j=0, m, binomial(m, j)^2*(x*A+x*O(x^n))^j)*x^m/m)));polcoeff(A, n, x)}

{a(n)=local(A=1+x);for(i=1,n,A=exp(sum(m=1, n, sum(j=0, n, binomial(m+j, j)^2*(x*A+x*O(x^n))^j)*(1-x*A)^(2*m+1)*x^m/m)));polcoeff(A, n, x)}

{a(n)=local(A=1+x);for(i=1,n,A=1/(1-x+x*O(x^n))*exp(sum(m=1,n,A^m*sum(k=0,m-1,binomial(m-1,k)*binomial(m,k)*x^k)/(1-x)^(2*m)*x^(2*m)/m) +x*O(x^n)));polcoeff(A,n)} /* Paul D. Hanna */

{a(n)=local(A=1+x);for(i=1,n,A=1/(1-x+x*O(x^n))*exp(sum(m=1,n,A^m*sum(k=0,n,binomial(m+k-1,k)*binomial(m+k,k)*x^k)*x^(2*m)/m) +x*O(x^n)));polcoeff(A,n)} /* Paul D. Hanna */

Vec(serreverse(x/(1+x+x^2+x^3)+O(x^66))/x) /* Joerg Arndt, Jun 10 2011 */

a(n) = (1/(n+1))*Sum_{j=0..floor(n/2)} binomial(n+1, n-2*j)*binomial(n+1, j). G.f. A(z) satisfies A=1+z*A+(z*A)^2+(z*A)^3. - Emeric Deutsch, Nov 29 2003
G.f.: F(x)/x where F(x) is the reversion of x/(1+x+x^2+x^3). - Joerg Arndt, Jun 10 2011
From Paul D. Hanna, Feb 13 2011: (Start)
O.g.f.: A(x) = exp( Sum_{n>=1} (Sum_{k=0..n} C(n,k)^2*x^k*A(x)^k) * x^n/n ).
O.g.f.: A(x) = exp( Sum_{n>=1} (Sum_{k>=0} C(n+k,k)^2*x^k*A(x)^k)*(1-x*A(x))^(2*n+1)* x^n/n ). (End)
From Paul D. Hanna, Feb 24 2011: (Start)
O.g.f.: A(x) = (1/(1-x))*exp( Sum_{n>=1} A(x)^n*(Sum_{k=0..n-1} C(n-1,k)*C(n,k)*x^k)/(1-x)^(2*n) * x^(2*n)/n ).
O.g.f.: A(x) = (1/(1-x))*exp( Sum_{n>=1} A(x)^n*(Sum_{k>=0} C(n+k-1,k)*C(n+k,k)*x^k) * x^(2*n)/n ). (End)
Let M = an infinite quadradiagonal matrix with all 1's in every diagonal: (sub, main, super, and super-super), and the rest zeros. V = vector [1,0,0,0,...]. The sequence = left column terms of M*V iterates. - Gary W. Adamson, Jun 06 2011
An infinite square production matrix M for the sequence is:
  1, 1, 0, 0, 0, 0, ...
  1, 0, 1, 0, 0, 0, ...
  2, 1, 0, 1, 0, 0, ...
  3, 2, 1, 0, 1, 0, ...
  4, 3, 2, 1, 0, 1, ...
  5, 4, 3, 2, 1, 0, ...
  ..., such that a(n) is the top left term of M^n. - Gary W. Adamson, Feb 21 2012
D-finite with recurrence: 2*(n+1)*(2*n+3)*(13*n-1)*a(n) = (143*n^3 + 132*n^2 - 17*n - 18)*a(n-1) + 4*(n-1)*(26*n^2 + 11*n - 6)*a(n-2) + 16*(n-2)*(n-1)*(13*n + 12)*a(n-3). - Vaclav Kotesovec, Sep 09 2013
a(n) ~ c*d^n/n^(3/2), where d = 1/12*((6371+624*sqrt(78))^(2/3)+11*(6371+624*sqrt(78))^(1/3)+217)/(6371+624*sqrt(78))^(1/3) = 3.610718613276... is the root of the equation -16-8*d-11*d^2+4*d^3=0 and c = sqrt(f/Pi) = 0.9102276936417..., where f = 1/9984*(9295 + (13*(45085576939 - 795629568*sqrt(78)))^(1/3) + (13*(45085576939 + 795629568*sqrt(78)))^(1/3)) is the root of the equation -128+1696*f-9295*f^2+3328*f^3=0. - Vaclav Kotesovec, Sep 10 2013
From Peter Bala, Jun 21 2015: (Start)
The coefficient of x^n in A(x)^r equals r/(n + r)*Sum_{k = 0..floor(n/2)} binomial(n + r,k)*binomial(n + r,n - 2*k) by the Lagrange-Bürmann formula.
O.g.f. A(x) = exp(Sum_{n >= 1} A005725(n)*x^n/n), where A005725(n) = Sum_{k = 0..floor(n/2)} binomial(n,k)*binomial(n,n - 2*k). Cf. A186241, A198951, A200731. (End)
a(n) = hypergeom([-n-1, (1-n)/2, -n/2], [1, 3/2], -1). - Vladimir Reshetnikov, Oct 15 2018

Name clarified by Andrew Howroyd, Dec 04 2017

A288942 Number A(n,k) of ordered rooted trees with n non-root nodes and all outdegrees <= k; square array A(n,k), n >= 0, k >= 0, read by antidiagonals.

Original entry on oeis.org

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, 9, 1, 0, 1, 1, 2, 5, 13, 21, 1, 0, 1, 1, 2, 5, 14, 36, 51, 1, 0, 1, 1, 2, 5, 14, 41, 104, 127, 1, 0, 1, 1, 2, 5, 14, 42, 125, 309, 323, 1, 0, 1, 1, 2, 5, 14, 42, 131, 393, 939, 835, 1, 0

Offset: 0

Alois P. Heinz, Sep 01 2017

Also the number of Dyck paths of semilength n with all ascent lengths <= k. A(4,2) = 9: /\/\/\/\, //\\/\/\, /\//\\/\, /\/\//\\, //\/\\/\, //\/\/\\, /\//\/\\, //\\//\\, //\//\\\.

Also the number of permutations p of [n] such that in 0p all up-jumps are <= k and no down-jump is larger than 1. An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here. A(4,2) = 9: 1234, 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2431.

			A(4,2) = 9:
.
.   o    o      o      o      o      o       o      o       o
.   |    |      |      |     / \    / \     / \    / \     / \
.   o    o      o      o    o   o  o   o   o   o  o   o   o   o
.   |    |     / \    / \   |          |  ( )        ( )  |   |
.   o    o    o   o  o   o  o          o  o o        o o  o   o
.   |   / \   |          |  |          |
.   o  o   o  o          o  o          o
.   |
.   o
.
Square array A(n,k) begins:
  1, 1,   1,   1,    1,    1,    1,    1,    1, ...
  0, 1,   1,   1,    1,    1,    1,    1,    1, ...
  0, 1,   2,   2,    2,    2,    2,    2,    2, ...
  0, 1,   4,   5,    5,    5,    5,    5,    5, ...
  0, 1,   9,  13,   14,   14,   14,   14,   14, ...
  0, 1,  21,  36,   41,   42,   42,   42,   42, ...
  0, 1,  51, 104,  125,  131,  132,  132,  132, ...
  0, 1, 127, 309,  393,  421,  428,  429,  429, ...
  0, 1, 323, 939, 1265, 1385, 1421, 1429, 1430, ...

Alois P. Heinz, Rows n = 0..140, flattened
N. Hein and J. Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015
Index entries for sequences related to rooted trees

Columns k=0..10 give: A000007, A000012, A001006, A036765, A036766, A036767, A036768, A036769, A291823, A291824, A291825.
Main diagonal (and upper diagonals) give A000108.
First lower diagonal gives A001453.
Cf. A203717.

b:= proc(u, o, k) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1, k), j=1..min(1, u))+
      add(b(u+j-1, o-j, k), j=1..min(k, o)))
    end:
A:= (n, k)-> b(0, n, k):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[u_, o_, k_] := b[u, o, k] = If[u + o == 0, 1, Sum[b[u - j, o + j - 1, k], {j, 1, Min[1, u]}] + Sum[b[u + j - 1, o - j, k], {j, 1, Min[k, o]}]];
A[n_, k_] := b[0, n, k];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Oct 27 2017, translated from Maple *)

T(n,k)=polcoeff(serreverse(x*(1-x)/(1-x*x^k) + O(x^2*x^n)), n+1);
for(n=0, 10, for(k=0, 10, print1(T(n, k), ", ")); print); \\ Andrew Howroyd, Nov 29 2017

A(n,k) = Sum_{j=0..k} A203717(n,j).
G.f. of column k: G(x)/x where G(x) is the reversion of x*(1-x)/(1-x^(k+1)). - Andrew Howroyd, Nov 30 2017
G.f. g_k(x) of column k satisfies: g_k(x) = Sum_{j=0..k} (x*g_k(x))^j. - Alois P. Heinz, May 05 2019
A(n,k) = Sum_{j=0..n/(k+1)} (-1)^j/(n+1) * binomial(n+1,j) * binomial(2*n-j*(k+1),n). [Hein Eq (10)] - R. J. Mathar, Oct 14 2022; corrected by Tijn Caspar de Leeuw, Jul 07 2024

A187925 Coefficient of x^n in (1+x+x^2+x^3+x^4)^n.

Original entry on oeis.org

1, 1, 3, 10, 35, 121, 426, 1520, 5475, 19855, 72403, 265233, 975338, 3598180, 13311000, 49360405, 183424355, 682870587, 2546441085, 9509714340, 35561166195, 133138728845, 499005557515, 1872137642125, 7030166054250, 26421479140746, 99376657487396

Offset: 0

Emanuele Munarini, Mar 16 2011

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A035343, A005191, A036766.

Column k=4 of A305161.

P:=PolynomialRing(Integers()); [Coefficients((1+x+x^2+x^3+x^4)^n)[n+1]: n in [0..26]]; // Vincenzo Librandi, Aug 09 2014

Pentanomial[n_, k_] := If[k == 0, 1, Coefficient[(1 + x + x^2 + x^3 + x^4)^n, x^k]]
Table[Pentanomial[n, n], {n, 0, 12}]

pentanomial(n,k):=coeff(expand((1+x+x^2+x^3+x^4)^n),x,k);
makelist(pentanomial(n,n),n,0,12);

a(n):=sum(binomial(n,r)*sum((sum(binomial(j,-r+n-m-j)*binomial(m,j),j,0,m))*binomial(r,m),m,0,r),r,0,n); /* Vladimir Kruchinin, Feb 03 2013 */

a(n):=sum((-1)^i*binomial(n,i)*binomial(2*n-5*i-1,n-5*i),i,0,n/5); /* Vladimir Kruchinin, Mar 28 2019 */

a(n) = polcoeff((1+x+x^2+x^3+x^4)^n, n); \\ Michel Marcus, Aug 09 2014

a(n) = sum(r=0..n, binomial(n,r)*sum(m=0..r, (sum(j=0..m, binomial(j,-r+n-m-j)*binomial(m,j)))*binomial(r,m))).  [Vladimir Kruchinin, Feb 03 2013]
G.f.: 1 + x*G'(x)/G(x) where G(x) is the g.f. of A036766. - Paul D. Hanna, Feb 03 2013
Recurrence: 3*n*(3*n-2)*(3*n-1)*(748*n^3 - 4136*n^2 + 7291*n - 4135)*a(n) = 2*(35156*n^6 - 247126*n^5 + 663756*n^4 - 870079*n^3 + 584710*n^2 - 190393*n + 23280)*a(n-1) + 5*(n-1)*(2244*n^5 - 14652*n^4 + 32367*n^3 - 28501*n^2 + 8564*n - 672)*a(n-2) + 100*(n-2)*(n-1)*(374*n^4 - 1881*n^3 + 2848*n^2 - 1475*n + 222)*a(n-3) + 125*(n-3)*(n-2)*(n-1)*(748*n^3 - 1892*n^2 + 1263*n - 232)*a(n-4). - Vaclav Kotesovec, Feb 11 2015
a(n) ~ c * d^n / sqrt(n), where d = 3.83443724902880556376524112660950145464... is the root of the equation -125-50*d-15*d^2-94*d^3+27*d^4 = 0, c = 0.3404440985692437948910444085315314358395... . - Vaclav Kotesovec, Feb 11 2015
a(n) = Sum_{i=0..n/5} (-1)^i*C(n,i)*C(2*n-5*i-1,n-5*i). - Vladimir Kruchinin, Mar 28 2019
From Peter Bala, Mar 31 2020: (Start)
a(p) == 1 (mod p^2) for any prime p > 5 (follows from Kruchinin's formula above). Cf. A002426. More generally, we may have a(p^k) == a(p^(k-1)) (mod p^(2*k)) for k >= 2 and any prime p.
The sequence b(n) := [x^n] ( F(x)/F(-x) )^n = [x^n] ( F(x)^2/F(x^2) )^n, where F(x) = 1 + x + x^2 + x^3 + x^4, may satisfy the stronger congruences b(p) == 2 (mod p^3) for prime p > 5 (checked up to p = 499). (End)

A203717 A Catalan triangle by rows.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 8, 4, 1, 1, 20, 15, 5, 1, 1, 50, 53, 21, 6, 1, 1, 126, 182, 84, 28, 7, 1, 1, 322, 616, 326, 120, 36, 8, 1, 1, 834, 2070, 1242, 495, 165, 45, 9, 1, 1, 2187, 6930, 4680, 1997, 715, 220, 55, 10, 1, 1, 5797, 23166, 17512, 7942, 3003, 1001, 286, 66, 11, 1

Offset: 1

Gary W. Adamson, Jan 04 2012

Row sums = the Catalan sequence starting with offset 1: (1, 2, 5, 14, 42,...).
T(n,k) is the number of Dyck n-paths whose maximum ascent length is k. - David Scambler, Aug 22 2012
T(n,k) is the number of ordered rooted trees with n non-root nodes and maximal outdegree k. T(4,3) = 4:
.    o      o      o      o
.    |     /|\    /|\    /|\
.    o    o o o  o o o  o o o
.   /|\   |        |        |
.  o o o  o        o        o   - Alois P. Heinz, Jun 29 2014
T(n,k) also is the number of permutations p of [n] such that in 0p the largest up-jump equals k and no down-jump is larger than 1. An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here. T(4,3) = 4: 1432, 3214, 3241, 3421. - Alois P. Heinz, Aug 29 2017

			First few rows of the array begin:
1,...1,...1,...1,...1,...;
1,...2,...4,...9,..21,...; = A001006
1,...2,...5,..13,..36,...; = A036765
1,...2,...5,..14,..41,...; = A036766
1,...2,...5,..14,..42,...; = A036767
... Taking finite differences of array terms starting from the top by columns, we obtain row terms of the triangle. First few rows of the triangle are:
  1;
  1,    1;
  1,    3,    1;
  1,    8,    4,    1;
  1,   20,   15,    5,    1;
  1,   50,   53,   21,    6,   1;
  1,  126,  182,   84,   28,   7,   1;
  1,  322,  616,  326,  120,  36,   8,  1;
  1,  834, 2070, 1242,  495, 165,  45,  9,  1;
  1, 2187, 6930, 4680, 1997, 715, 220, 55, 10, 1;
  ...
Example: Row 4 of the triangle = (1, 8, 4, 1) = the finite differences of (1, 9, 13, 14), column 4 of the array. Term (3,4) = 13 of the array is the upper left term of M^4, where M is an infinite square production matrix with four diagonals of 1's starting at (1,2), (1,1), (2,1), and (3,1); with the rest zeros.

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A000108, A001006, A036765, A036766, A036767, A291680, A288942.
Columns k=1-3 give: A057427, A140662(n-1) for n>1, A303271.
T(2n,n) gives A291662.
T(2n+1,n+1) gives A005809.
T(n,ceiling(n/2)) gives A303259.

b:= proc(n, t, k) option remember; `if`(n=0, 1, `if`(t>0,
      add(b(j-1, k$2)*b(n-j, t-1, k), j=1..n), b(n-1, k$2)))
    end:
T:= (n, k)-> b(n, k-1$2) -`if`(k=1, 0, b(n, k-2$2)):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Jun 29 2014
# second Maple program:
b:= proc(u, o, k) option remember; `if`(u+o=0, 1,
      add(b(u-j, o+j-1, k), j=1..min(1, u))+
      add(b(u+j-1, o-j, k), j=1..min(k, o)))
    end:
T:= (n, k)-> b(0, n, k)-`if`(k=0, 0, b(0, n, k-1)):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Aug 28 2017

b[n_, t_, k_] := b[n, t, k] = If[n == 0, 1, If[t > 0, Sum[b[j-1, k, k]*b[n - j, t-1, k], {j, 1, n}], b[n-1, k, k]]]; T[n_, k_] := b[n, k-1, k-1] - If[k == 1, 0, b[n, k-2, k-2]]; Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-François Alcover, May 27 2016, after Alois P. Heinz *)

from sympy.core.cache import cacheit
@cacheit
def b(u, o, k): return 1 if u + o==0 else sum([b(u - j, o + j - 1, k) for j in range(1, min(1, u) + 1)]) + sum([b(u + j - 1, o - j, k) for j in range(1, min(k, o) + 1)])
def T(n, k): return b(0, n, k) - (0 if k==0 else b(0, n, k - 1))
for n in range(1, 16): print([T(n, k) for k in range(1, n + 1)]) # Indranil Ghosh, Aug 30 2017

Finite differences of antidiagonals of an array in which n-th array row is generated from powers of M, extracting successive upper left terms. M for n-th row of the array is an infinite square production matrix composed of (n+1) diagonals of 1's and the rest zeros. Given the upper left term of the array is (1,1), the diagonals begin at (1,2), (1,1), (2,1), (3,1), (4,1),...

T(n,k) = A288942(n,k) - A288942(n,k-1). - Alois P. Heinz, Sep 01 2017

A261588 5-Modular Catalan Numbers C_{n,5}.

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 131, 420, 1375, 4576, 15431, 52603, 180957, 627340, 2189430, 7685785, 27118855, 96123508, 342099955, 1221979374, 4379357895, 15742077045, 56742085710, 205041235750, 742647580815, 2695585363122, 9803561513316, 35720226039252, 130373533268780

Offset: 0

Nickolas Hein, Aug 25 2015

nonn

Definition: Given a primitive k-th root of unity w, a binary operation a*b=a+wb, and sufficiently general fixed complex numbers x_0, ..., x_n, the k-modular Catalan numbers C_{n,k} enumerate parenthesizations of x_0*x_1*...*x_n that give distinct values.
Theorem: C_{n,k} enumerates the following objects:
(1) binary trees with n internal nodes avoiding a certain subtree (i.e., comb_k^{+1}),
(2) plane trees with n+1 nodes whose non-root nodes have degree less than k,
(3) Dyck paths of length 2n avoiding a down-step followed immediately by k consecutive up-steps,
(4) partitions with n nonnegative parts bounded by the staircase partition (n-1,n-2,...,1,0) such that each positive number appears fewer than k times,
(5) standard 2-by-n Young tableaux whose top row avoids contiguous labels of the form i,j+1,j+2,...,j+k for all i(6) permutations of {1,2,...,n} avoiding 1-3-2 and 23...(k+1)1.

			The Catalan number C_6=132 counts the parenthesizations of x_1*...*x_7 where * is arbitrary. Defining * and w as above and writing x_i compactly as xi, we have x1*(x2*(x3*(x4*(x5*(x6*(x7)))))) = x1+wx2+w^2x3+w^3x4+w^4x5+x6+wx7 = x1*(x2*(x3*(x4*(x5*(x6)))))*(x7). For n=6 and k=5, these are the only parenthesizations that give the same value for x1*...*x7, so C_{6,5}=132-1=131.

Andrew Howroyd, Table of n, a(n) for n = 0..200
Nickolas Hein and Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015.
Nickolas Hein and Jia Huang, Modular Catalan Numbers, European Journal of Combinatorics 61 (2017), 197-218.

Column k=5 of A295679.
C_{n,1} is the all 1's sequence A000012. For C_{n,k} with k=2,3,4 see A011782, A005773, A159772. For k=6,7,8,9 see A261589, A261590, A261591, A261592.
Cf. A036766.

terms = 30; col[k_] := Module[{G}, G = InverseSeries[x*(1 - x)/(1 - x^k) + O[x]^terms, x]; CoefficientList[1/(1 - G), x]];
col[5] (* Jean-François Alcover, Dec 05 2017, after Andrew Howroyd *)

Vec(1/(1-serreverse(x*(1-x)/(1-x^5) + O(x*x^25)))) \\ Andrew Howroyd, Dec 04 2017

def C(k):
    print(1)
    for n in range(1,51):
        f = ((1-x^k)/(1-x))^n # ((x+1)^2-x^2*(x/(x+1))^(k-2))^n
        f = f.simplify_full()
        C = 0
        for i in range(n):
            C = C + (n-i)*f.coefficient(x,i)/n
        print(C)
time C(5)

sum( 1<=l<=n, (l/n)sum( m_1+...+m_k=n and m_2+2m_3+...+(k-1)m_k=n-l, MC(n;m_1,...,m_k) ) ), where MC(n;m_1,...,m_k) is the multinomial coefficient associated to the multiset (m_1,...,m_k).
G.f.: 1/(1-x*G(x)) where G(x) is g.f. of A036766. - Andrew Howroyd, Dec 04 2017
Recurrence: 3*n*(3*n - 2)*(3*n - 1)*(1309*n^5 - 14388*n^4 + 60934*n^3 - 124236*n^2 + 121825*n - 45948)*a(n) = (299761*n^8 - 3779182*n^7 + 19492177*n^6 - 53378731*n^5 + 84116656*n^4 - 77081911*n^3 + 39268230*n^2 - 9775512*n + 829440)*a(n-1) - 5*(119119*n^8 - 1601215*n^7 + 8920729*n^6 - 26755339*n^5 + 46820344*n^4 - 48217102*n^3 + 27785664*n^2 - 7773768*n + 712800)*a(n-2) - 25*(n-3)*(1309*n^7 - 11770*n^6 + 38824*n^5 - 62344*n^4 + 74887*n^3 - 107794*n^2 + 101952*n - 33120)*a(n-3) - 125*(n-4)*(n-3)*(1309*n^6 - 10461*n^5 + 28528*n^4 - 30261*n^3 + 7999*n^2 + 3390*n - 1080)*a(n-4) - 625*(n-5)*(n-4)*(n-3)*(1309*n^5 - 7843*n^4 + 16472*n^3 - 14672*n^2 + 5148*n - 504)*a(n-5). - Vaclav Kotesovec, Dec 05 2017

A337513 G.f. A(x) satisfies: A(x) = 1 - Sum_{k=1..4} (x * A(x))^k.

Original entry on oeis.org

1, -1, 0, 1, 0, -1, -5, 13, 5, -43, 4, 98, 122, -638, -246, 2912, -537, -9419, -1648, 47005, 2243, -232237, 87988, 904267, -351692, -4123026, 1726126, 20257940, -14035151, -86846040, 73352891, 387126945, -358259621, -1853868355, 2081413376

Offset: 0

Ilya Gutkovskiy, Aug 30 2020

sign

Cf. A000078, A007440, A036766, A337512, A337514.

nmax = 34; A[] = 0; Do[A[x] = 1 - Sum[(x A[x])^k, {k, 1, 4}] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]
nmax = 35; CoefficientList[(1/x) InverseSeries[Series[x/(1 - x - x^2 - x^3 - x^4), {x, 0, nmax}], x], x]
b[m_, r_, k_] := b[m, r, k] = If[m + r == 0, 1, Sum[b[m - j, r + j - 1, k], {j, 1, Min[1, m]}] - Sum[b[m + j - 1, r - j, k], {j, 1, Min[k, r]}]]; a[n_] := b[0, n, 4]; Table[a[n], {n, 0, 34}]

G.f.: A(x) = (1/x) * Series_Reversion(x / (1 - x - x^2 - x^3 - x^4)).

A365508 Number of n-vertex binary trees that do not contain 0[0(0[0(00)])] as a subtree.

Original entry on oeis.org

1, 2, 5, 14, 41, 123, 375, 1157, 3603, 11304, 35683, 113219, 360805, 1154140

Offset: 1

Torsten Muetze, Sep 07 2023

By 'binary tree' we mean a rooted, ordered tree which is either empty, denoted by 0, or it has both a left subtree L and a right subtree R (which can be empty), and then it is denoted by (LR) if it is attached by a contiguous edge to its parent, [LR] if attached by a non-contiguous edge, or LR if it is does not have a parent, i.e., if is the root. A contiguous edge in the pattern tree corresponds to a parent-child relation in the host tree (as in Rowland's paper), whereas a non-contiguous edge in the pattern tree corresponds to an ancestor-descendant relation in the host tree (as in the paper by Dairyko, Pudwell, Tyner, and Wynn).
Number of n-vertex binary trees that do not contain P as a subtree, where P is one of 0[0(0((00)0))], 0[0((00)(00))], 0[0((0(00))0)], 0[(00)(0(00))], 0[(00)((00)0)], 0[(0(00))(00)], 0[((00)0)(00)], 0[(0((00)0))0],  0[((00)(00))0], 0[((0(00))0)0], 0(([0(00)]0)0), 0(([(00)0]0)0).
Number of restricted growth strings of set partitions of {1,...,n} that avoid the two patterns 1212 and p, where p is one of 12232, 12113, 12322, 11213.

CombOS - Combinatorial Object Server, Generate binary trees
Michael Dairyko, Lara Pudwell, Samantha Tyner, and Casey Wynn, Non-contiguous pattern avoidance in binary trees, arXiv:1203.0795 [math.CO], 2012.
Michael Dairyko, Lara Pudwell, Samantha Tyner, and Casey Wynn, Non-contiguous pattern avoidance in binary trees, Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.
Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.
Petr Gregor, Torsten Mütze, and Namrata, Pattern-Avoiding Binary Trees-Generation, Counting, and Bijections, Leibniz Int'l Proc. Informatics (LIPIcs), 34th Int'l Symp. Algor. Comp. (ISAAC 2023). See pp. 33.12, 33.13.
Eric S. Rowland, Pattern avoidance in binary trees, arXiv:0809.0488 [math.CO], 2010.
Eric S. Rowland, Pattern avoidance in binary trees, J. Comb. Theory A 117 (6) (2010) 741-758.

Cf. A007051 for pattern 0[0[0[0[00]]]], i.e., same tree shape, but all edges non-contiguous.
Cf. A036766 for pattern 0(0(0(0(00)))), i.e., same tree shape, but all edges contiguous.
Cf. A365509, A365510.

A365509 Number of n-vertex binary trees that do not contain 0(0[0(0(00))]) as a subtree.

Original entry on oeis.org

1, 2, 5, 14, 41, 124, 383, 1202, 3819, 12255, 39651, 129190, 423469, 1395425

Offset: 1

Torsten Muetze, Sep 07 2023

By 'binary tree' we mean a rooted, ordered tree which is either empty, denoted by 0, or it has both a left subtree L and a right subtree R (which can be empty), and then it is denoted by (LR) if it is attached by a contiguous edge to its parent, [LR] if attached by a non-contiguous edge, or LR if it is does not have a parent, i.e., if is the root. A contiguous edge in the pattern tree corresponds to a parent-child relation in the host tree (as in Rowland's paper), whereas a non-contiguous edge in the pattern tree corresponds to an ancestor-descendant relation in the host tree (as in the paper by Dairyko, Pudwell, Tyner, and Wynn).

Number of n-vertex binary trees that do not contain 0(0[((00)0)0]) as a subtree.

CombOS - Combinatorial Object Server, Generate binary trees
Michael Dairyko, Lara Pudwell, Samantha Tyner, and Casey Wynn, Non-contiguous pattern avoidance in binary trees, arXiv:1203.0795 [math.CO], 2012.
Michael Dairyko, Lara Pudwell, Samantha Tyner, and Casey Wynn, Non-contiguous pattern avoidance in binary trees, Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.
Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.
Petr Gregor, Torsten Mütze, and Namrata, Pattern-Avoiding Binary Trees-Generation, Counting, and Bijections, Leibniz Int'l Proc. Informatics (LIPIcs), 34th Int'l Symp. Algor. Comp. (ISAAC 2023). See pp. 33.12, 33.13.
Eric S. Rowland, Pattern avoidance in binary trees, arXiv:0809.0488 [math.CO], 2010.
Eric S. Rowland, Pattern avoidance in binary trees, J. Comb. Theory A 117 (6) (2010) 741-758.

Cf. A007051 for pattern 0[0[0[0[00]]]], i.e., same tree shape, but all edges non-contiguous.
Cf. A036766 for pattern 0(0(0(0(00)))), i.e., same tree shape, but all edges contiguous.
Cf. A365508, A365510.

A161746 The number of equivalence classes of n-leaf binary trees with respect to contiguous pattern avoidance.

Original entry on oeis.org

1, 1, 1, 2, 3, 7, 15, 43, 136

Offset: 1

Eric Rowland, Jun 17 2009

			Representatives of the a(6) = 7 equivalence classes of 6-leaf binary trees are given in A036766, A159768, A159769, A159770, A159771, A159772, and A159773.

Andrey T. Cherkasov and Dmitri Piontkovski, Wilf classes of non-symmetric operads, arXiv:2105.08880 [math.CO], 2021.
L. Pudwell, Pattern avoidance in trees, (slides from a talk, mentions many sequences), 2012. - _N. J. A. Sloane_, Jan 03 2013
Eric S. Rowland, Pattern avoidance in binary trees, arXiv:0809.0488 [math.CO], 2008-2010.
Eric S. Rowland, Pattern avoidance in binary trees, J. Comb. Theory A 117 (6) (2010) 741-758.

Cf. A099952.

Per Cherkasov and Piontkovski, a(8) corrected by Eric Rowland, May 22 2021

a(9) from Eric Rowland, Apr 25 2024

Showing 1-9 of 9 results.

cp's OEIS Frontend

A036765 Number of ordered rooted trees with n non-root nodes and all outdegrees <= three.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

PARI

PARI

Formula

Extensions

A288942 Number A(n,k) of ordered rooted trees with n non-root nodes and all outdegrees <= k; square array A(n,k), n >= 0, k >= 0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A187925 Coefficient of x^n in (1+x+x^2+x^3+x^4)^n.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

Maxima

Maxima

PARI

Formula

A203717 A Catalan triangle by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A261588 5-Modular Catalan Numbers C_{n,5}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A337513 G.f. A(x) satisfies: A(x) = 1 - Sum_{k=1..4} (x * A(x))^k.

Views

Author

Keywords

Crossrefs