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

1, 1, 2, 5, 14, 42, 131, 421, 1385, 4642, 15795, 54418, 189454, 665471, 2355510, 8393461, 30084695, 108394449, 392356788, 1426137550, 5203211200, 19048447855, 69951072700, 257609070810, 951172531880, 3520465229446, 13058843476526, 48540377627407

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

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

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Colin Defant and Kai Zheng, Stack-Sorting with Consecutive-Pattern-Avoiding Stacks, arXiv:2008.12297 [math.CO], 2020.
• Vladimir Kruchinin and D. V. Kruchinin, Composita and their properties, arXiv:1103.2582 [math.CO], 2011-2013.
• Vladimir Kruchinin and D. V. Kruchinin, Composita and their properties, J. Ana. Num. Theor. Vol. 2, No. 2, 2014, 37-44.
• 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.
• L. 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

Column k=5 of A288942.

Programs

Maple

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) ];
# 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(5, o)))
    end:
a:= n-> b(0, n):
seq(a(n), n=0..30);  # Alois P. Heinz, Aug 28 2017

Mathematica

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 *)
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, 5];
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/sum(k=0,5,x^k)+O(x^(n+2))),n+1)) \\ Ralf Stephan

Formula

G.f. A(x) satisfies A(x) = 1 + sum(n=1..5, (x*A(x))^n). - Vladimir Kruchinin, Feb 22 2011

Extensions

Name clarified by Andrew Howroyd, Dec 04 2017