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, 235929600000000000000000

Offset: 2

Author

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

Keywords

• nonn
• changed

Comments

From Amanda Priestley, Aug 20 2025: (Start)

a(n+1) is the total number of ties in all parking functions of length n for n >= 1, where a tie in a parking function x = (x_1, x_2, ..., x_n) is a position where x_i = x_{i+1}.

a(n+1) is the total number of small descents in all parking functions of length n for n >= 1, where a small descent in a parking function x = (x_1, x_2, ..., x_n) is a position where x_i = x_{i+1} + 1. (End)

Examples

			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)
		

Links

• Kyle Celano, Jennifer Elder, Kimberly P. Hadaway, Pamela E. Harris, Amanda Priestley, and Gabe Udell, Inversions in parking functions, arXiv:2508.11587 [math.CO], 2025.
• 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.

Programs

Mathematica

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

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  */

PARI

apply( {A071720(n)=(n-2)*n^(n-3)}, [2..22]) \\ M. F. Hasler, Aug 21 2025

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