A354017 Number of subtrees of all distinct free trees with n nodes.

0, 1, 3, 6, 21, 52, 165, 466, 1489, 4564, 15339

Offset

0,3

Comments

The number of trees with n unlabeled nodes is given by A000055. The present sequence is the total number of distinct subtrees of each tree with n unlabeled nodes. This excludes the empty set and so a(0) = 0.

Links

Table of n, a(n) for n=0..10.

Adam A. Arfaoui, Matlab program

Example

For n = 3 the a(3) = 6 solutions are found by counting subtrees on the A000055(3) = 1 tree.
Tree (3,1):
  o-o-o ->
  (o    ) +
  (  o  ) +
  (    o) +
  (o-o  ) +
  (  o-o) +
  (o-o-o)
          = 6.
a(3) = number of subtrees of (3,1) = 6.
For n = 4 there are A000055(4) = 2 distinct trees.
Tree (4,1):
  o-o-o-o ->
  (o      ) +
  (  o    ) +
  (    o  ) +
  (      o) +
  (o-o    ) +
  (  o-o  ) +
  (    o-o) +
  (o-o-o  ) +
  (  o-o-o) +
  (o-o-o-o)
            = 10.
Tree (4,2):
  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
          = 11.
a(4) = number of subtrees of (4,1) + number of subtrees of (4,2) = 10 + 11 = 21.

Crossrefs

Cf. A000055.

Sequence in context: A136331 A063683 A200380 * A151396 A148604 A148605

Adjacent sequences: A354014 A354015 A354016 * A354018 A354019 A354020

Keyword

nonn,more

Author

Adam A. Arfaoui, May 14 2022

Status

approved