cp's OEIS Frontend

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

%I A270593 #18 Feb 05 2020 08:24:25
%S A270593 0,1,3,9,38,250,2367,29197,441212,7874244,161950445,3770473399,
%T A270593 98009367282,2813394489022,88387455559067,3016497635377545,
%U A270593 111127442649962168,4395316276005329608,185766120783135345177,8355290720655784462507,398470047793625748742670,20084626943220497590901346
%N A270593 Total number of subtrees of the complete simple undirected graph K_n on n vertices.
%C A270593 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.
%H A270593 Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/3082248/graph-theory-trees">Graph Theory - Trees</a>, answer by user Thomas Lesgourgues, Jan 22 2019.
%F A270593 a(n) = Sum_{k=1..n} binomial(n,k)*(k^(k-2)).
%F A270593 a(n) ~ exp(exp(-1)) * n^(n-2). - _Vaclav Kotesovec_, Apr 02 2016
%e A270593 For an empty graph, having no vertices, a(0)=0.
%e A270593 a(1)=1 as there is a trivial tree consisting of a single vertex.
%e A270593 When number of vertices n=2, a(n)=2+1=3: 2 singles A, B; 1 pair: A-B.
%e A270593 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.
%e A270593 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.
%e A270593 a(8)=8+28+168+1120+7000+36288+134456+262144=441212.
%o A270593 (PARI) a(n) = sum(k=1, n, binomial(n,k)*(k^(k-2))); \\ _Michel Marcus_, Mar 20 2016
%Y A270593 Cf. A000272 (number of trees on n labeled nodes).
%K A270593 nonn
%O A270593 0,3
%A A270593 _Viktar Karatchenia_, Mar 19 2016
%E A270593 More terms from _Michel Marcus_, Mar 20 2016