|
Search: id:A124454
|
|
|
| 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. |
|
+0
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
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
LINKS
|
David Eppstein (eppstein(AT)ics.uci.edu), Dec 17 2006, 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.
|
|
PROGRAM
|
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: A003453 A011901 A109471 this_sequence A013932 A010335 A084576
Adjacent sequences: A124451 A124452 A124453 this_sequence A124455 A124456 A124457
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
David Eppstein (eppstein(AT)ics.uci.edu), Dec 17 2006
|
|
|
Search completed in 0.002 seconds
|
