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

1, 1, 3, 7, 17, 42, 105, 267, 684, 1775, 4639, 12238, 32491, 86859, 233496, 631082, 1713613, 4673455, 12795426, 35159212, 96927479, 268021520, 743188706, 2066071045, 5757360011, 16079027344, 44997313684, 126166307275, 354384737204, 997083779801, 2809751278062

Offset: 2

Author

Joerg Arndt and Alois P. Heinz, Jun 29 2014

Keywords

• nonn

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 2..800

Crossrefs

Column k=1 of A244454.

Cf. A106640 (the same for ordered rooted trees).

Programs

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, 1$2) -b(n-1$2, 2$2):
seq(a(n), n=2..35);

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, 1, 1] - b[n - 1, n - 1, 2, 2]; Table[a[n], {n, 2, 35}] (* Jean-François Alcover, Feb 06 2015, after Maple *)

Formula

a(n) = A000081(n) - A001678(n+1).