A288942 -id:A288942 - 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

A292085 Number A(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes or outdegrees larger than 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, 2, 0, 1, 1, 2, 4, 3, 0, 1, 1, 2, 5, 9, 6, 0, 1, 1, 2, 5, 11, 23, 11, 0, 1, 1, 2, 5, 12, 30, 58, 23, 0, 1, 1, 2, 5, 12, 32, 80, 156, 46, 0, 1, 1, 2, 5, 12, 33, 87, 228, 426, 98, 0, 1, 1, 2, 5, 12, 33, 89, 251, 656, 1194, 207, 0

Offset: 1

Alois P. Heinz, Sep 08 2017

			:               T(4,3) = 4             :
:                                      :
:       o       o         o       o    :
:      / \     / \       / \     /|\   :
:     o   N   o   o     o   N   o N N  :
:    / \     ( ) ( )   /|\     ( )     :
:   o   N    N N N N  N N N    N N     :
:  ( )                                 :
:  N N                                 :
:                                      :
Square array A(n,k) begins:
  1,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,   2,   2,   2,   2,   2,   2, ...
  0,  2,   4,   5,   5,   5,   5,   5, ...
  0,  3,   9,  11,  12,  12,  12,  12, ...
  0,  6,  23,  30,  32,  33,  33,  33, ...
  0, 11,  58,  80,  87,  89,  90,  90, ...
  0, 23, 156, 228, 251, 258, 260, 261, ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Index entries for sequences related to rooted trees

Columns k=1-10 give: A063524, A001190, A268172, A292210, A292211, A292212, A292213, A292214, A292215, A292216.
Main diagonal gives A000669.
Cf. A244372, A288942, A292086.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n

b[n_, i_, v_, k_] := b[n, i, v, k] = If[n == 0, If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0, If[v == n, 1, Sum[Binomial[A[i, k] + j - 1, j]*b[n - i*j, i - 1, v - j, k], {j, 0, Min[n/i, v]}]]]];
A[n_, k_] := A[n, k] = If[n < 2, n, Sum[b[n, n + 1 - j, j, k], {j, 2, Min[n, k]}]];
Table[Table[A[n, 1 + d - n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

A(n,k) = Sum_{j=1..k} A292086(n,j).

A292086 Number T(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that k is the maximum of 1 and the node outdegrees; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 6, 2, 1, 0, 6, 17, 7, 2, 1, 0, 11, 47, 22, 7, 2, 1, 0, 23, 133, 72, 23, 7, 2, 1, 0, 46, 380, 230, 77, 23, 7, 2, 1, 0, 98, 1096, 751, 256, 78, 23, 7, 2, 1, 0, 207, 3186, 2442, 861, 261, 78, 23, 7, 2, 1, 0, 451, 9351, 8006, 2897, 887, 262, 78, 23, 7, 2, 1

Offset: 1

Alois P. Heinz, Sep 08 2017

			:   T(4,2) = 2        :   T(4,3) = 2      : T(4,4) = 1 :
:                     :                   :            :
:       o       o     :      o       o    :     o      :
:      / \     / \    :     / \     /|\   :   /( )\    :
:     o   N   o   o   :    o   N   o N N  :  N N N N   :
:    / \     ( ) ( )  :   /|\     ( )     :            :
:   o   N    N N N N  :  N N N    N N     :            :
:  ( )                :                   :            :
:  N N                :                   :            :
:                     :                   :            :
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,   1;
  0,  2,   2,   1;
  0,  3,   6,   2,  1;
  0,  6,  17,   7,  2,  1;
  0, 11,  47,  22,  7,  2, 1;
  0, 23, 133,  72, 23,  7, 2, 1;
  0, 46, 380, 230, 77, 23, 7, 2, 1;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
Index entries for sequences related to rooted trees

Columns k=1-10 give: A063524, A001190 (for n>1), A292229, A292230, A292231, A292232, A292233, A292234, A292235, A292236.
Row sums give A000669.
Limit of reversed rows gives A292087.
Cf. A244372, A288942, A292085.

b:= proc(n, i, v, k) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n A(n, k)-`if`(k=1, 0, A(n, k-1)):
seq(seq(T(n, k), k=1..n), n=1..15);

b[n_, i_, v_, k_] := b[n, i, v, k] = If[n == 0, If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0, If[v == n, 1, Sum[Binomial[A[i, k] + j - 1, j]*b[n - i*j, i - 1, v - j, k], {j, 0, Min[n/i, v]}]]]];
A[n_, k_] := A[n, k] = If[n < 2, n, Sum[b[n, n + 1 - j, j, k], {j, 2, Min[n, k]}]];
T[n_, k_] := A[n, k] - If[k == 1, 0, A[n, k - 1]];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 15}] // Flatten (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

T(n,k) = A292085(n,k) - A292085(n,k-1) for k>2, T(n,1) = A292085(n,1).

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

Original entry on oeis.org

1, 1, 2, 5, 14, 41, 125, 393, 1265, 4147, 13798, 46476, 158170, 543050, 1878670, 6542330, 22915999, 80682987, 285378270, 1013564805, 3613262795, 12924536005, 46373266470, 166856922125, 601928551824, 2176616383346, 7888184659826, 28645799759632, 104224861693855

Offset: 0

N. J. A. Sloane

nonn

a(n) is the number of Dyck n-paths that avoid UUUUU=(U^5). For example, a(5)=41 counts all 42 Dyck 5-paths except (U^5)(D^5). - David Callan, Sep 25 2006
Number of n-leaf binary trees that do not contain (()(()(()(()(()()))))) as a subtree. - Eric Rowland, Jun 17 2009
a(n) is the number of ordered unlabeled rooted trees on n+1 nodes where each node has no more than 4 children. - Geoffrey Critzer, Jan 05 2013

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
CombOS - Combinatorial Object Server, Generate binary trees
Colin Defant and Kai Zheng, Stack-Sorting with Consecutive-Pattern-Avoiding Stacks, arXiv:2008.12297 [math.CO], 2020.
M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.
Filippo Disanto and Thomas Wiehe, Some instances of a sub-permutation problem on pattern avoiding permutations, arXiv preprint arXiv:1210.6908 [math.CO], 2012-2014.
Nickolas Hein and Jia Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015.
L. Pudwell, Pattern avoidance in trees (slides from a talk, mentions many sequences), 2012. - From N. J. A. Sloane, Jan 03 2013
Lajos Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).
Index entries for sequences related to rooted trees

The sequence of sequences A000007 (0^n), A000012 (1's), A001006 (Motzkin), A036765, A036766, ... tends to A000108 (Catalan).

Column k=4 of A288942.

r := 4; [ 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) ];

nn=20;f[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[Series[0==f[x]-x -x f[x]-x f[x]^2-x f[x]^3-x f[x]^4,{x,0,nn}],x];Table[a[n],{n,0,nn}]/.sol  (* Geoffrey Critzer, Jan 05 2013 *)
Table[1/(n+1)*Sum[(-1)^j*Binomial[n+1,j]*Binomial[2*n-5*j,n],{j,0,Floor[n/5]}],{n,0,20}] (* Vaclav Kotesovec, Mar 13 2014 *)
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, 4];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

a(n)=if(n<0,0,polcoeff(serreverse(x/polcyclo(5)+O(x^(n+2))),n+1)) /* Ralf Stephan */

G.f.: A(x) satisfies A(x) = 1+x*A(x)+x^2*A(x)^2+x^3*A(x)^3+x^4*A(x)^4. - Vladimir Kruchinin, Feb 22 2011
a(n) ~ sqrt(s/(1 + 3*r*s + 6*r^2*s^2)) / (2*n^(3/2)*sqrt(Pi)*r^(n+1)), where r = 0.2607944621478111633... and s = 2.176953284456253116... are roots of the system of equations r + 2*r^2*s + 3*r^3*s^2 + 4*r^4*s^3 = 1, 1 + r*s + r^2*s^2 + r^3*s^3 + r^4*s^4 = s. - Vaclav Kotesovec, Mar 13 2014
Conjecture: -3*(3*n+2)*(133*n-347)*(3*n+4)*(n+1)*a(n) +(111457*n^4-364730*n^3+228995*n^2+19310*n-33312)*a(n-1) +5*(-68503*n^4+34661
8*n^3-590627*n^2+397748*n-90564)*a(n-2) -25*(n-2)*(1933*n^3-9435*n^2+14354*n-7518)*a(n-3) -125*(n-2)*(n-3)*(1333*n^2-4384*n+2718)*
a(n-4) -625*(733*n-400)*(n-2)*(n-3)*(n-4)*a(n-5)=0. - R. J. Mathar, Aug 04 2015

Name clarified by Andrew Howroyd, Dec 04 2017

A295679 Array read by antidiagonals: T(n,k) = k-Modular Catalan numbers C_{n,k} (n >= 0, k > 0).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 4, 1, 1, 1, 2, 5, 8, 1, 1, 1, 2, 5, 13, 16, 1, 1, 1, 2, 5, 14, 35, 32, 1, 1, 1, 2, 5, 14, 41, 96, 64, 1, 1, 1, 2, 5, 14, 42, 124, 267, 128, 1, 1, 1, 2, 5, 14, 42, 131, 384, 750, 256, 1, 1, 1, 2, 5, 14, 42, 132, 420, 1210, 2123, 512, 1

Offset: 0

Andrew Howroyd, Nov 30 2017

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.
Columns of the array converge rowwise to A000108. The diagonal k=n-1 is A001453. - Andrey Zabolotskiy, Dec 02 2017

			Array begins (n >= 0, k > 0):
======================================================
n\k| 1   2    3    4    5    6    7    8    9   10
---|--------------------------------------------------
0  | 1   1    1    1    1    1    1    1    1    1 ...
1  | 1   1    1    1    1    1    1    1    1    1 ...
2  | 1   2    2    2    2    2    2    2    2    2 ...
3  | 1   4    5    5    5    5    5    5    5    5 ...
4  | 1   8   13   14   14   14   14   14   14   14 ...
5  | 1  16   35   41   42   42   42   42   42   42 ...
6  | 1  32   96  124  131  132  132  132  132  132 ...
7  | 1  64  267  384  420  428  429  429  429  429 ...
8  | 1 128  750 1210 1375 1420 1429 1430 1430 1430 ...
9  | 1 256 2123 3865 4576 4796 4851 4861 4862 4862 ...
...

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

Columns 3..9 are A005773, A159772, A261588, A261589, A261590, A261591, A261592.

Cf. A288942, A000108, A001453.

A295679 := proc(n,k)
    if n = 0 then
        1;
    else
        add((-1)^j/n*binomial(n,j)*binomial(2*n-j*k,n+1),j=0..(n-1)/k) ;
    end if ;
end proc:
seq(seq( A295679(n,d-n),n=0..d-1),d=1..12) ; # R. J. Mathar, Oct 14 2022

rows = cols = 12;
col[k_] := Module[{G}, G = InverseSeries[x*(1-x)/(1-x^k) + O[x]^cols, x]; CoefficientList[1/(1 - G), x]];
A = Array[col, cols];
T[n_, k_] := A[[k, n+1]];
Table[T[n-k+1, k], {n, 0, rows-1}, {k, n+1, 1, -1}] // Flatten (* Jean-François Alcover, Dec 05 2017, adapted from PARI *)

T(n,k)=polcoeff(1/(1-serreverse(x*(1-x)/(1-x^k) + O(x^max(2,n+1)))), n);
for(n=0, 10, for(k=1, 10, print1(T(n, k), ", ")); print);

G.f. of column k: 1/(1-G(x)) where G(x) is the reversion of x*(1-x)/(1-x^k).

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

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

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 131, 421, 1385, 4642, 15795, 54418, 189454, 665471, 2355510, 8393461, 30084695, 108394449, 392356788, 1426137550, 5203211200, 19048447855, 69951072700, 257609070810, 951172531880, 3520465229446, 13058843476526, 48540377627407

Offset: 0

N. J. A. Sloane

nonn

Empirical: number of Dyck n-paths avoiding UUUUUU (or DDDDDD). e.g. of the 132 Dyck 6-paths U^6D^6 contains UUUUUU so a(6)=131. - David Scambler, Mar 24 2011

a(n) is the number of ordered unlabeled rooted trees on n+1 nodes where each node has no more than 5 children. - Geoffrey Critzer, Jan 05 2013

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Colin Defant and Kai Zheng, Stack-Sorting with Consecutive-Pattern-Avoiding Stacks, arXiv:2008.12297 [math.CO], 2020.
Vladimir Kruchinin and D. V. Kruchinin, Composita and their properties, arXiv:1103.2582 [math.CO], 2011-2013.
Vladimir Kruchinin and D. V. Kruchinin, Composita and their properties, J. Ana. Num. Theor. Vol. 2, No. 2, 2014, 37-44.
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.
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).
Index entries for sequences related to rooted trees

Column k=5 of A288942.

r := 5; [ 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(5, o)))
    end:
a:= n-> b(0, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 28 2017

nn=12;f[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[Series[0==f[x]-x -x f[x]-x f[x]^2-x f[x]^3-x f[x]^4- x f[x]^5,{x,0,nn}],x];Table[a[n],{n,0,nn}]/.sol  (* Geoffrey Critzer, Jan 05 2013 *)
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, 5];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

a(n)=if(n<0,0,polcoeff(serreverse(x/sum(k=0,5,x^k)+O(x^(n+2))),n+1)) \\ Ralf Stephan

G.f. A(x) satisfies A(x) = 1 + sum(n=1..5, (x*A(x))^n). - Vladimir Kruchinin, Feb 22 2011

Name clarified by Andrew Howroyd, Dec 04 2017

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

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1429, 4852, 16730, 58422, 206192, 734332, 2635680, 9524301, 34622207, 126520393, 464517300, 1712650520, 6338433840, 23538973950, 87690410580, 327611738790, 1227178265182, 4607940112396, 17341126763366, 65395548619912

Offset: 0

N. J. A. Sloane

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
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.
L. Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).
Index entries for sequences related to rooted trees

Column k=7 of A288942.

r := 7; [ 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(7, o)))
    end:
a:= n-> b(0, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 28 2017

b[u_, o_] := b[u, o] = If[u + o == 0, 1, Sum[b[u - j, o + j - 1], {j, 1, Min[1, u]}] + Sum[b[u + j - 1, o - j], {j, 1, Min[7, o]}]];
a[n_] := b[0, n];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Oct 27 2017, after Alois P. Heinz *)

a(n)=if(n<0,0,polcoeff(serreverse(x/sum(k=0,7,x^k)+O(x^(n+2))),n+1)) /* Ralf Stephan */

G.f. A(x) satisfies: A(x) = 1 + Sum_{k=1..7} x^k*A(x)^k. - Ilya Gutkovskiy, May 03 2019

Name clarified by Andrew Howroyd, Dec 04 2017

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

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 428, 1421, 4807, 16510, 57421, 201824, 715768, 2558167, 9204651, 33315919, 121218195, 443107245, 1626546453, 5993256280, 22158739970, 82182744284, 305670888560, 1139892935454, 4261095044346, 15964169665031, 59933390160322

Offset: 0

N. J. A. Sloane

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Vladimir Kruchinin and D. V. Kruchinin, Composita and their properties, arXiv:1103.2582 [math.CO], 2011-2013.
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.
Lajos Takacs, Enumeration of rooted trees and forests, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).
Index entries for sequences related to rooted trees

Column k=6 of A288942.

r := 6; [ 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(6, o)))
    end:
a:= n-> b(0, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 28 2017

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, 6];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

a(n)=if(n<0,0,polcoeff(serreverse(x/polcyclo(7)+O(x^(n+2))),n+1)) /* Ralf Stephan */

G.f. A(x) satisfies A(x)=1+sum(n=1..6, (x*A(x))^n). - Vladimir Kruchinin, Feb 22 2011

Name clarified by Andrew Howroyd, Dec 04 2017

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

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4861, 16785, 58708, 207557, 740520, 2662812, 9640581, 35112513, 128563215, 472951884, 1747233370, 6479450415, 24111470952, 90006390290, 336953657070, 1264770431964, 4758911027946, 17946417454046, 67818937355227, 256781370248500

Offset: 0

Alois P. Heinz, Sep 01 2017

nonn

Also the number of Dyck paths of semilength n with all ascent lengths <= eight.
Also the number of permutations p of [n] such that in 0p all up-jumps are <= eight 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.
Differs from A000108 first at n = 9.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
N. Hein and J. Huang, Modular Catalan Numbers, arXiv:1508.01688 [math.CO], 2015
Index entries for sequences related to rooted trees

Column k=8 of A288942.

Cf. A000108.

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(8, o)))
    end:
a:= n-> b(0, n):
seq(a(n), n=0..30);

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, 8];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

Vec(serreverse(x*(1-x)/(1-x*x^8) + O(x*x^25))) \\ Andrew Howroyd, Nov 29 2017

G.f.: G(x)/x where G(x) is the reversion of x*(1-x)/(1-x^9). - Andrew Howroyd, Nov 30 2017

G.f. A(x) satisfies: A(x) = 1 + Sum_{k=1..8} x^k*A(x)^k. - Ilya Gutkovskiy, May 03 2019

Showing 1-10 of 13 results. Next

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

A292085 Number A(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes or outdegrees larger than k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A292086 Number T(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that k is the maximum of 1 and the node outdegrees; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A295679 Array read by antidiagonals: T(n,k) = k-Modular Catalan numbers C_{n,k} (n >= 0, k > 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A203717 A Catalan triangle by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple