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,3

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

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

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

Prog

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

Crossrefs

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

Column k=4 of A288942.

Sequence in context: A159768 A128739 A356698 * A366024 A222589 A243870

Adjacent sequences: A036763 A036764 A036765 * A036767 A036768 A036769

Keyword

nonn

Author

N. J. A. Sloane

Extensions

Name clarified by Andrew Howroyd, Dec 04 2017

Status

approved