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

1, 2, 5, 10, 22, 45, 97, 206, 450, 982, 2178, 4849, 10904, 24630, 56010, 127911, 293546, 676156, 1563371, 3626148, 8436378, 19680276, 46026617, 107890608, 253450710, 596572386, 1406818758, 3323236237, 7862958390, 18632325318, 44214569099, 105061603968

Offset: 3

Author

Joerg Arndt and Alois P. Heinz, Jun 27 2014

Keywords

• nonn

Links

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

Crossrefs

Column k=2 of A244372.

Cf. A001190, A036656, A086317, A086318.

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

Formula

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

a(n) ~ c * d^n / n^(3/2), where d = 2.4832535361726368... = A086317 and c = 0.7916031835775118... = A086318. - Vaclav Kotesovec, Jun 27 2014