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

0, 1, 8, 75, 864, 12005, 196608, 3720087, 80000000, 1929229929, 51597803520, 1516443410339, 48594782035968, 1686702392578125, 63050394783186944, 2525667398391013935, 107946249863639334912, 4903504030649559850577

Offset

2,3

Links

Table of n, a(n) for n=2..19.

N. Eaton, W. Kook and L. Thoma, Monotonicity for complete graphs, preprint, 2003.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009.

Marko Riedel, Math StackExchange, Derivation of the closed form using combinatorial classes from *Analytic Combinatorics* by Flajolet and Sedgewick.

Formula

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

a(n) = (n - 1)! * [x^(n-1)] LambertW(-x)*(1 + LambertW(-x))/x. - Andrei Asinowski, Sep 07 2015

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

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

Example

a(3) = 1 because K_{3}-e is a tree.
From Rainer Rosenthal, Nov 18 2020: (Start)
a(4) = 8 because K_{4}-e has these spanning trees:
       A         A         A         A
      /           \       /           \
     o - o     o - o     o   o     o   o
        /       \         \ /       \ /
       Z         Z         Z         Z
.
      4.1       4.2       4.3       4.4
.
.
       A         A         A         A
      / \       / \       /           \
     o   o     o   o     o - o     o - o
      \           /       \           /
       Z         Z         Z         Z
.
      4.5       4.6       4.7       4.8
(End)

Mathematica

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

Prog

(Maxima)
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  */

Crossrefs

Sequence in context: A067306 A361528 A261065 * A273998 A111685 A302814

Adjacent sequences: A071717 A071718 A071719 * A071721 A071722 A071723

Keyword

nonn

Author

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

Status

approved