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

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)

Links

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

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 and symmetric complete bipartite 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

a[n_] := (n-2)*n^(n-3); Table[a[i], {i, 2, 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  */
(PARI) apply( {A071720(n)=(n-2)*n^(n-3)}, [2..22]) \\ M. F. Hasler, Aug 21 2025

Crossrefs

Sequence in context: A067306 A361528 A261065 * A391313 A273998 A111685

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