A244399 Number of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) 3.

1, 2, 6, 16, 43, 113, 300, 787, 2074, 5460, 14391, 37960, 100275, 265187, 702307, 1862463, 4945952, 13152441, 35023003, 93385548, 249330208, 666539949, 1784102735, 4781254117, 12828545419, 34459732110, 92668129050, 249469906115, 672296028786, 1813606782459

Offset

4,2

Links

Alois P. Heinz, Table of n, a(n) for n = 4..1000

Formula

a(n) = A000598(n) - A001190(n+1) = A000598(n) - A036656(n+1).

a(n) ~ c * d^n / n^(3/2), where d = 1/A261340 = 2.81546003317615... and c = 0.5178759064... . - Vaclav Kotesovec, Jun 27 2014

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-> b(n-1$2, 3$2) -`if`(k=0, 0, b(n-1$2, 2$2)):
seq(a(n), n=4..35);

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]}]]//FullSimplify]; a[n_] := b[n-1, n-1, 3, 3] - If[n == 0, 0, b[n-1, n-1, 2, 2]]; Table[a[n], {n, 4, 35}] (* Jean-François Alcover, Feb 09 2015, after Maple *)

Crossrefs

Column k=3 of A244372.

Cf. A000598, A001190, A036656.

Sequence in context: A191694 A224232 A217661 * A291142 A027994 A319503

Adjacent sequences: A244396 A244397 A244398 * A244400 A244401 A244402

Keyword

nonn

Author

Joerg Arndt and Alois P. Heinz, Jun 27 2014

Status

approved