A292555 Number of rooted unlabeled trees on n nodes where each node has at most 10 children.

1, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4765, 12483, 32964, 87785, 235305, 634628, 1720524, 4686842, 12820920, 35206475, 97010705, 268154003, 743351390, 2066090876, 5756490561, 16074597300, 44980514021, 126109353817, 354202275766, 996517941454

Offset: 0

Author

Marko Riedel, Sep 18 2017

Keywords

• nonn

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Marko Riedel, Trees with bounded degree.

Crossrefs

Cf. A000081, A001190, A000598, A036718, A036721, A036722, A182378, A244372, A292553, A292554, A292556.

Column k=10 of A299038.

Programs

Maple

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
a:= n-> `if`(n=0, 1, b(n-1$2, 10$2)):
seq(a(n), n=0..35);  # Alois P. Heinz, Sep 20 2017

Mathematica

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i < 1, 0, Sum[ Binomial[b[i - 1, i - 1, k, k] + j - 1, j]*b[n - i*j, i - 1, t - j, k], {j, 0, Min[t, n/i]}]]];
a[n_] := If[n == 0, 1, b[n - 1, n - 1, 10, 10]];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jun 04 2018, after Alois P. Heinz *)

Formula

Functional equation of G.f. is T(z) = z + z*Sum_{q=1..10} Z(S_q)(T(z)) with Z(S_q) the cycle index of the symmetric group. Alternate FEQ is

T(z) = 1 + z*Z(S_10)(T(z)).

a(n) = Sum_{j=1..10} A244372(n,j) for n>0, a(0) = 1. - Alois P. Heinz, Sep 20 2017

a(n) / a(n+1) ~ 0.338329194566131211670667671160855741193081902868090986608524... - Robert A. Russell, Feb 11 2023