%I #26 Jul 11 2022 16:05:02
%S 0,1,3,6,21,52,165,466,1489,4564,15339
%N Number of subtrees of all distinct free trees with n nodes.
%C 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.
%H Adam A. Arfaoui, <a href="/A354017/a354017.txt">Matlab program</a>
%e For n = 3 the a(3) = 6 solutions are found by counting subtrees on the A000055(3) = 1 tree.
%e Tree (3,1):
%e o-o-o ->
%e (o ) +
%e ( o ) +
%e ( o) +
%e (o-o ) +
%e ( o-o) +
%e (o-o-o)
%e = 6.
%e a(3) = number of subtrees of (3,1) = 6.
%e For n = 4 there are A000055(4) = 2 distinct trees.
%e Tree (4,1):
%e o-o-o-o ->
%e (o ) +
%e ( o ) +
%e ( o ) +
%e ( o) +
%e (o-o ) +
%e ( o-o ) +
%e ( o-o) +
%e (o-o-o ) +
%e ( o-o-o) +
%e (o-o-o-o)
%e = 10.
%e Tree (4,2):
%e o-o-o ->
%e |
%e o
%e (o ) +
%e ( o ) +
%e ( o) +
%e ( ) +
%e o
%e (o-o ) +
%e ( o-o) +
%e ( o ) +
%e |
%e o
%e (o-o-o) +
%e (o-o ) +
%e |
%e o
%e ( o-o) +
%e |
%e o
%e (o-o-o)
%e |
%e o
%e = 11.
%e a(4) = number of subtrees of (4,1) + number of subtrees of (4,2) = 10 + 11 = 21.
%Y Cf. A000055.
%K nonn,more
%O 0,3
%A _Adam A. Arfaoui_, May 14 2022