login
Number of subtrees of all distinct free trees with n nodes.
1

%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