

A270593


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


1



0, 1, 3, 9, 38, 250, 2367, 29197, 441212, 7874244, 161950445, 3770473399, 98009367282, 2813394489022, 88387455559067, 3016497635377545, 111127442649962168, 4395316276005329608, 185766120783135345177, 8355290720655784462507, 398470047793625748742670, 20084626943220497590901346
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


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^(k2) spanning trees. To calculate the total number of spanning trees for all subgraphs with kvertices, the number of combinations must be multiplied by the number of spanning trees: binomial(n, k) * (k^(k2)). To get the total number of all subtrees, all possible graph sizes, that is k=[1..n], must be accounted for.


LINKS



FORMULA

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


EXAMPLE

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: AB.
For n=3, a(n)=3+3+3=9: 3 singles A, B, C; 3 pairs: AB, AC, BC; 3 triples: ABBC, BCCA, CAAB.
For n=4, a(n)=4+6+12+16=38: 4 singles A, B, C, D; 6 pairs: AB, AC, AD, BC, BD, CD; 12 triples: ABAC, ABAD, ABBC, ABBD, ACAD, ACBC, ACCD, ADBD, ADCD, BCCD, BDBC, BDCD; 16 4tuples: ABACAD, ABACBD, ABACCD, ABADBC, ABADCD, ABBCBD, ABBCCD, ABBDCD, ACADBC, ACADBD, ACBCBD, ACBCCD, ACBDCD, ADBCBD, ADBCCD, ADBDCD. It is worth noting that ABCD is not a tree, because there is no path from A to C. Also, ABACBC is a cycle, not a tree.
a(8)=8+28+168+1120+7000+36288+134456+262144=441212.


PROG

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


CROSSREFS

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


KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



