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, 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

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

Cf. A092781.

Sequence in context: A169739 A109471 A279032 * A335631 A013932 A302550

Adjacent sequences: A124451 A124452 A124453 * A124455 A124456 A124457

Keyword

easy,nonn

Author

David Eppstein, Dec 17 2006

Status

approved