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

A159772 Number of n-leaf binary trees that do not contain (()((((()())())())())) as a subtree.

Original entry on oeis.org

1, 1, 2, 5, 14, 41, 124, 384, 1210, 3865, 12482, 40677, 133572, 441468, 1467296, 4900760, 16439370, 55357305, 187050302, 633998079, 2154950454, 7343407521, 25082709012, 85858848820, 294480653064, 1011871145116, 3482837144984, 12006861566684, 41454180382688

Offset: 1

Eric Rowland, Apr 23 2009

nonn

By 'binary tree' we mean a rooted, ordered tree in which each vertex has either 0 or 2 children.
a(n) is also the number of Dyck words of semilength n-1 with no DUUUU.
Also, number of ordered rooted trees with n nodes and all non-root nodes having outdegrees < 4. - Andrew Howroyd, Dec 04 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
CombOS - Combinatorial Object Server, Generate binary trees
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
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.
Eric S. Rowland, Pattern avoidance in binary trees, arXiv:0809.0488 [math.CO], 2008-2010.

Column k=4 of A295679.

Cf. A036765, A064580.

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

a(n):=if n=1 then 1 else sum(k*sum(binomial(n-1,j)*sum(binomial(j,i-j)*binomial(n-j-1,3*j-n-k-i+1),i,j,n-k+j-1),j,0,n-1),k,1,n-1)/(n-1); /* Vladimir Kruchinin, Oct 23 2011 */

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

G.f. f(x) satisfies (1 - 4 x) f(x)^3 + (6 x - 1) x f(x)^2 - 4 x^3 f(x) + x^4 = 0.
a(n) = sum(k=1..n-1, k*sum(j=0..n-1, binomial(n-1,j)*sum(i=j..n-k+j-1, binomial(j,i-j)*binomial(n-j-1,3*j-n-k-i+1))))/(n-1), n>1. a(0)=0, a(1)=1. - Vladimir Kruchinin, Oct 23 2011
Conjecture: 2*(n-1)*(2*n-3)*a(n) +(-43*n^2+172*n-177)*a(n-1) +4*(44*n^2-266*n+411)*a(n-2) +8*(-43*n^2+358*n-741)*a(n-3) +96*(3*n^2-29*n+69)*a(n-4) -128*(n-4)*(n-6)*a(n-5) +512*(n-6)*(n-7)*a(n-6)=0. - R. J. Mathar, May 30 2014
G.f.: x/(1-x*G(x)) where G(x) is g.f. of A036765. - Andrew Howroyd, Dec 04 2017
From Vaclav Kotesovec, Dec 05 2017: (Start)
Recurrence (of order 4): 2*(n-1)*(2*n - 3)*(13*n^2 - 75*n + 104)*a(n) = 3*(117*n^4 - 1039*n^3 + 3315*n^2 - 4513*n + 2216)*a(n-1) - 12*(39*n^4 - 368*n^3 + 1268*n^2 - 1893*n + 1032)*a(n-2) - 16*(n-4)*(13*n^3 - 75*n^2 + 122*n - 54)*a(n-3) - 64*(n-5)*(n-4)*(13*n^2 - 49*n + 42)*a(n-4).
a(n) ~ sqrt(r*s*(r - s + 2*s^2) / (2*Pi*(r - 6*r^2 - 3*s + 12*r*s))) / (n^(3/2) * r^n), where r = 0.2769531794372340984240353119411920830379502290822... and s = 0.8081460429543529393193017440354060980373344931954... are real roots of the system of equations r^4 + r*(-1 + 6*r)*s^2 + (1 - 4*r)*s^3 = 4*r^3*s, s*(12*r^2 + 3*s - 2*r*(1 + 6*s)) = 4*r^3. (End)
a(n+1) = Sum_{k=0..n} A064580(n,k). - Georg Fischer, Jul 20 2023

cp's OEIS Frontend

A064581 Duplicate of A064580.

Views

Author

Keywords

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

A159772 Number of n-leaf binary trees that do not contain (()((((()())())())())) as a subtree.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

A136751 G.f.: A(x) = ...o x/(1-x^4) o x/(1-x^3) o x/(1-x^2) o x/(1-x), composition of functions x/(1-x^n) for n = 1,2,3,...

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI