A244457 Number of unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals 3.

1, 0, 0, 1, 2, 2, 4, 7, 12, 20, 34, 56, 98, 167, 284, 484, 835, 1433, 2467, 4250, 7345, 12700, 22004, 38154, 66266, 115224, 200623, 349654, 610126, 1065739, 1863547, 3261672, 5714277, 10020092, 17586014, 30890654, 54305289, 95542387, 168221056, 296401979

Offset

4,5

Links

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

Formula

a(n) ~ c * d^n / n^(3/2), where d = 1.8239199077079..., c = 0.49573400799... . - Vaclav Kotesovec, Jul 11 2014

Example

a(7) = 1:
      o
     /|\
    o o o
   /|\
  o o o

Maple

b:= proc(n, i, t, k) option remember; `if`(n=0, `if`(t in [0, k],
      1, 0), `if`(i<1 or t>n, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
      b(n-i*j, i-1, max(0, t-j), k), j=0..n/i)))
    end:
a:= n-> b(n-1$2, 3$2) -b(n-1$2, 4$2):
seq(a(n), n=4..45);

Mathematica

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, If[t == 0 || t == k, 1, 0], If[i < 1, 0, Sum[Binomial[b[i - 1, i - 1, k, k] + j - 1, j]*b[n - i*j, i - 1, Max[0, t - j], k], {j, 0, n/i}]] // FullSimplify]; a[n_] := b[n - 1, n - 1, 3, 3] - b[n - 1, n - 1, 4, 4]; Table[a[n], {n, 4, 45}] (* Jean-François Alcover, Feb 06 2015, after Maple *)

Crossrefs

Column k=3 of A244454.

Cf. A244532.

Sequence in context: A095325 A179183 A325786 * A325908 A153970 A067953

Adjacent sequences: A244454 A244455 A244456 * A244458 A244459 A244460

Keyword

nonn

Author

Joerg Arndt and Alois P. Heinz, Jun 29 2014

Status

approved