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

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

Author

N. J. A. Sloane

Keywords

• nonn

Comments

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

Links

• 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

Crossrefs

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

Column k=4 of A288942.

Programs

Maple

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) ];

Mathematica

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 *)

PARI

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

Formula

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

Extensions

Name clarified by Andrew Howroyd, Dec 04 2017