%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