cp's OEIS Frontend

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

%I A036767 #63 Nov 17 2020 17:28:06
%S A036767 1,1,2,5,14,42,131,421,1385,4642,15795,54418,189454,665471,2355510,
%T A036767 8393461,30084695,108394449,392356788,1426137550,5203211200,
%U A036767 19048447855,69951072700,257609070810,951172531880,3520465229446,13058843476526,48540377627407
%N A036767 Number of ordered rooted trees with n non-root nodes and all outdegrees <= five.
%C A036767 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
%C A036767 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
%H A036767 Alois P. Heinz, <a href="/A036767/b036767.txt">Table of n, a(n) for n = 0..1000</a>
%H A036767 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 A036767 Vladimir Kruchinin and D. V. Kruchinin, <a href="http://arxiv.org/abs/1103.2582">Composita and their properties</a>, arXiv:1103.2582 [math.CO], 2011-2013.
%H A036767 Vladimir Kruchinin and D. V. Kruchinin, <a href="http://www.naturalspublishing.com/files/published/yzmx634l9k644k.pdf">Composita and their properties</a>, J. Ana. Num. Theor. Vol. 2, No. 2, 2014, 37-44.
%H A036767 Nickolas Hein and Jia Huang, <a href="http://arxiv.org/abs/1508.01688">Modular Catalan Numbers</a>, arXiv:1508.01688 [math.CO], 2015.
%H A036767 Nickolas Hein and Jia Huang, <a href="https://doi.org/10.1016/j.ejc.2016.11.004">Modular Catalan Numbers</a>, European Journal of Combinatorics 61 (2017), 197-218.
%H A036767 L. Takacs, <a href="http://www.appliedprobability.org/data/files/TMS%20articles/18_1_1.pdf">Enumeration of rooted trees and forests</a>, Math. Scientist 18 (1993), 1-10, esp. Eq. (6).
%H A036767 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A036767 G.f. A(x) satisfies A(x) = 1 + sum(n=1..5, (x*A(x))^n). - _Vladimir Kruchinin_, Feb 22 2011
%p A036767 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) ];
%p A036767 # second Maple program:
%p A036767 b:= proc(u, o) option remember; `if`(u+o=0, 1,
%p A036767       add(b(u-j, o+j-1), j=1..min(1, u))+
%p A036767       add(b(u+j-1, o-j), j=1..min(5, o)))
%p A036767     end:
%p A036767 a:= n-> b(0, n):
%p A036767 seq(a(n), n=0..30);  # _Alois P. Heinz_, Aug 28 2017
%t A036767 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 *)
%t A036767 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 A036767 a[n_] := b[0, n, 5];
%t A036767 Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Nov 07 2017, after _Alois P. Heinz_ *)
%o A036767 (PARI) a(n)=if(n<0,0,polcoeff(serreverse(x/sum(k=0,5,x^k)+O(x^(n+2))),n+1)) \\ _Ralf Stephan_
%Y A036767 Column k=5 of A288942.
%K A036767 nonn
%O A036767 0,3
%A A036767 _N. J. A. Sloane_
%E A036767 Name clarified by _Andrew Howroyd_, Dec 04 2017