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

1, 2, 6, 17, 49, 136, 386, 1081, 3044, 8549, 24052, 67642, 190426, 536205, 1510920, 4259418, 12014682, 33907056, 95740913, 270468869, 764450150, 2161638413, 6115252839, 17307553766, 49005101669, 138811296158, 393351362321, 1115072623713, 3162183392471

Offset

5,2

Links

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

Formula

a(n) = A036718(n) - A000598(n).

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

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

Crossrefs

Column k=4 of A244372.

Cf. A000598, A036718.

Sequence in context: A365244 A036365 A299162 * A052536 A122100 A122099

Adjacent sequences: A244397 A244398 A244399 * A244401 A244402 A244403

Keyword

nonn

Author

Joerg Arndt and Alois P. Heinz, Jun 27 2014

Status

approved