OFFSET
1,2
LINKS
David Eppstein, Table of n, a(n) for n = 1..52
EXAMPLE
a(4) = 11 because in the four-node tree with one degree three node and three leaves, there are eight ways of forming a subtree with the central node and some subset of leaves and three more subtrees with just one leaf, for a total of 11 subtrees. The other possible four-node tree (a path) has fewer subtrees.
PROG
Can be computed by a straightforward dynamic program too lengthy to list here in which we keep, for each n, a list of pairs (number of subtrees, number of subtrees that contain the root) for different n-node trees. Only the undominated pairs need be kept so the time is polynomial in n.
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
David Eppstein, Dec 17 2006
STATUS
approved