login
Number of spanning trees in K_{n}-e, the complete graph on n nodes minus an edge (n > 1).
1

%I #42 Jun 26 2024 15:26:08

%S 0,1,8,75,864,12005,196608,3720087,80000000,1929229929,51597803520,

%T 1516443410339,48594782035968,1686702392578125,63050394783186944,

%U 2525667398391013935,107946249863639334912,4903504030649559850577,235929600000000000000000

%N Number of spanning trees in K_{n}-e, the complete graph on n nodes minus an edge (n > 1).

%H N. Eaton, W. Kook and L. Thoma, <a href="https://web.archive.org/web/20070418085358/http://www.math.uri.edu/~eaton/UnimodKnn.pdf">Monotonicity for complete graphs</a>, preprint, 2003.

%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009.

%H Marko Riedel, Math StackExchange, <a href="https://math.stackexchange.com/questions/1832958/">Derivation of the closed form using combinatorial classes from *Analytic Combinatorics* by Flajolet and Sedgewick.</a>

%F a(n) = (n - 2) * n^(n - 3) for n > 1.

%F a(n) = (n - 1)! * [x^(n-1)] LambertW(-x)*(1 + LambertW(-x))/x. - _Andrei Asinowski_, Sep 07 2015

%F a(n) = 2*Sum_{i=0..n-3}(binomial(n - 2, i + 1)*((i + 1)^(i + 1)*(n - i - 1)^(n - i - 4))). - _Vladimir Kruchinin_, Apr 20 2016

%F a(n) = (n - 2)! [z^(n - 2)] (T(z)/(1 - T(z)))*exp(T(z))^2 with T(z) the tree function T(z) = Sum_{n>=1} n^(n - 1) z^n/n!, which reads in the notation from 'Analytic Combinatorics' (see link) as SEQ_{>=1}(T) x SET(T) x SET(T). - _Marko Riedel_, Apr 15 2021

%e a(3) = 1 because K_{3}-e is a tree.

%e From _Rainer Rosenthal_, Nov 18 2020: (Start)

%e a(4) = 8 because K_{4}-e has these spanning trees:

%e A A A A

%e / \ / \

%e o - o o - o o o o o

%e / \ \ / \ /

%e Z Z Z Z

%e .

%e 4.1 4.2 4.3 4.4

%e .

%e .

%e A A A A

%e / \ / \ / \

%e o o o o o - o o - o

%e \ / \ /

%e Z Z Z Z

%e .

%e 4.5 4.6 4.7 4.8

%e (End)

%t f[n_] := (n-2)*n^{n-3}; Table[f[i], {i, 20}]

%o (Maxima)

%o a(n):=2*sum(binomial(n-2,i+1)*((i+1)^(i+1)*(n-i-1)^(n-i-4)),i,0,n-3); /* _Vladimir Kruchinin_, Apr 20 2016 */

%K nonn

%O 2,3

%A N. Eaton, W. Kook, L. Thoma (andrewk(AT)math.uri.edu), Jan 16 2004