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

Links

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

Formula

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

Example

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

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

Crossrefs

Column k=1 of A244454.

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

Sequence in context: A086395 A020730 A003440 * A102071 A363142 A191627

Adjacent sequences: A244452 A244453 A244454 * A244456 A244457 A244458

Keyword

nonn

Author

Joerg Arndt and Alois P. Heinz, Jun 29 2014

Status

approved