A270593 Total number of subtrees of the complete simple undirected graph K_n on n vertices.

0, 1, 3, 9, 38, 250, 2367, 29197, 441212, 7874244, 161950445, 3770473399, 98009367282, 2813394489022, 88387455559067, 3016497635377545, 111127442649962168, 4395316276005329608, 185766120783135345177, 8355290720655784462507, 398470047793625748742670, 20084626943220497590901346

Offset: 0

Author

Viktar Karatchenia, Mar 19 2016

Keywords

• nonn

Comments

A complete graph on n vertices can have subgraphs, having from 1 to n vertices inclusively. To choose k vertices from n vertices, there are binomial(n, k) combinations. Having chosen the k vertices, the complete subgraph on these k vertices, according to A000272, has k^(k-2) spanning trees. To calculate the total number of spanning trees for all subgraphs with k-vertices, the number of combinations must be multiplied by the number of spanning trees: binomial(n, k) * (k^(k-2)). To get the total number of all subtrees, all possible graph sizes, that is k=[1..n], must be accounted for.

Examples

			For an empty graph, having no vertices, a(0)=0.
a(1)=1 as there is a trivial tree consisting of a single vertex.
When number of vertices n=2, a(n)=2+1=3: 2 singles A, B; 1 pair: A-B.
For n=3, a(n)=3+3+3=9: 3 singles A, B, C; 3 pairs: A-B, A-C, B-C; 3 triples: A-B|B-C, B-C|C-A, C-A|A-B.
For n=4, a(n)=4+6+12+16=38: 4 singles A, B, C, D; 6 pairs: A-B, A-C, A-D, B-C, B-D, C-D; 12 triples: A-B|A-C, A-B|A-D, A-B|B-C, A-B|B-D, A-C|A-D, A-C|B-C, A-C|C-D, A-D|B-D, A-D|C-D, B-C|C-D, B-D|B-C, B-D|C-D; 16 4-tuples: A-B|A-C|A-D, A-B|A-C|B-D, A-B|A-C|C-D, A-B|A-D|B-C, A-B|A-D|C-D, A-B|B-C|B-D, A-B|B-C|C-D, A-B|B-D|C-D, A-C|A-D|B-C, A-C|A-D|B-D, A-C|B-C|B-D, A-C|B-C|C-D, A-C|B-D|C-D, A-D|B-C|B-D, A-D|B-C|C-D, A-D|B-D|C-D. It is worth noting that A-B|C-D is not a tree, because there is no path from A to C. Also, A-B|A-C|B-C is a cycle, not a tree.
a(8)=8+28+168+1120+7000+36288+134456+262144=441212.
		

Links

• Mathematics Stack Exchange, Graph Theory - Trees, answer by user Thomas Lesgourgues, Jan 22 2019.

Crossrefs

Cf. A000272 (number of trees on n labeled nodes).

Programs

PARI

a(n) = sum(k=1, n, binomial(n,k)*(k^(k-2))); \\ Michel Marcus, Mar 20 2016

Formula

a(n) = Sum_{k=1..n} binomial(n,k)*(k^(k-2)).

a(n) ~ exp(exp(-1)) * n^(n-2). - Vaclav Kotesovec, Apr 02 2016

Extensions

More terms from Michel Marcus, Mar 20 2016