login
A124454
Maximum possible number of subtrees of an n-node unrooted tree in which each node has maximum degree three (equivalently, rooted binary trees in which some internal nodes may have only one child). A subtree is a nonempty contiguous set of nodes, not necessarily including all descendants of the root.
1
1, 3, 6, 11, 17, 28, 40, 63, 90, 143, 197, 304, 436, 699, 963, 1490, 2147, 3460, 4816, 7527, 10914, 17687, 24461, 38008, 54940, 88803, 124011, 194426, 282443, 458476, 634510, 986577, 1426659, 2306822, 3222182, 5052901, 7341298, 11918091
OFFSET
1,2
LINKS
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
Cf. A092781.
Sequence in context: A169739 A109471 A279032 * A335631 A013932 A302550
KEYWORD
easy,nonn
AUTHOR
David Eppstein, Dec 17 2006
STATUS
approved