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,2

Links

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

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

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 *)

Crossrefs

Column k=2 of A244372.

Cf. A001190, A036656, A086317, A086318.

Sequence in context: A045621 A026655 A336484 * A100938 A018004 A124329

Adjacent sequences: A244395 A244396 A244397 * A244399 A244400 A244401

Keyword

nonn

Author

Joerg Arndt and Alois P. Heinz, Jun 27 2014

Status

approved