A036766 - OEIS

%I #92 May 30 2026 16:40:04

%S 1,1,2,5,14,41,125,393,1265,4147,13798,46476,158170,543050,1878670,

%T 6542330,22915999,80682987,285378270,1013564805,3613262795,

%U 12924536005,46373266470,166856922125,601928551824,2176616383346,7888184659826,28645799759632,104224861693855

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

%C 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

%C Number of n-leaf binary trees that do not contain (()(()(()(()(()()))))) as a subtree. - _Eric Rowland_, Jun 17 2009

%C 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

%H Vincenzo Librandi, <a href="/A036766/b036766.txt">Table of n, a(n) for n = 0..1000</a>

%H Paul Barry, <a href="https://arxiv.org/abs/2001.08799">Characterizations of the Borel triangle and Borel polynomials</a>, arXiv:2001.08799 [math.CO], 2020.

%H CombOS - Combinatorial Object Server, <a href="http://combos.org/btree">Generate binary trees</a>

%H Colin Defant and Kai Zheng, <a href="https://arxiv.org/abs/2008.12297">Stack-Sorting with Consecutive-Pattern-Avoiding Stacks</a>, arXiv:2008.12297 [math.CO], 2020.

%H M. Dziemianczuk, <a href="https://doi.org/10.1016/j.disc.2014.07.024">Enumerations of plane trees with multiple edges and Raney lattice paths</a>, Discrete Mathematics 337 (2014): 9-24.

%H Filippo Disanto and Thomas Wiehe, <a href="https://arxiv.org/abs/1210.6908">Some instances of a sub-permutation problem on pattern avoiding permutations</a>, arXiv preprint arXiv:1210.6908 [math.CO], 2012-2014.

%H Nickolas Hein and Jia Huang, <a href="https://arxiv.org/abs/1508.01688">Modular Catalan Numbers</a>, arXiv:1508.01688 [math.CO], 2015.

%H L. Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/notredame.pdf">Pattern avoidance in trees</a> (slides from a talk, mentions many sequences), 2012. - From N. J. A. Sloane, Jan 03 2013

%H Lajos Takacs, <a href="https://drive.google.com/file/d/1K7dq0uhgY4aB-oIssyW4ipq16SvyE2Pu/view">Enumeration of rooted trees and forests</a>, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%F 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

%F 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

%F 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

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

%F a(n-4) -625*(733*n-400)*(n-2)*(n-3)*(n-4)*a(n-5)=0. - _R. J. Mathar_, Aug 04 2015

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

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

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

%t 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]}]];

%t a[n_] := b[0, n, 4];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Nov 07 2017, after _Alois P. Heinz_ *)

%o (PARI) a(n)=if(n<0,0,polcoeff(serreverse(x/polcyclo(5)+O(x^(n+2))),n+1)) /* _Ralf Stephan_ */

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

%Y Column k=4 of A288942.

%K nonn,changed

%O 0,3

%A _N. J. A. Sloane_

%E Name clarified by _Andrew Howroyd_, Dec 04 2017