OFFSET
1,3
COMMENTS
Equivalently, a(n) is the number of orderings of the edges of the complete graph of n vertices such that the minimal spanning tree (e.g., obtained by running Kruskal's algorithm with the edges in that order) is a specific path.
It appears that this is a subsequence of A253950. Specifically, a(n) appears at index m - n + 3, where m = binomial(n,2) is the number of edges of the complete graph on n vertices.
LINKS
Jamie Tucker-Foltz, Table of n, a(n) for n = 1..16
Eric Babson, Moon Duchin, Annina Iseli, Pietro Poggi-Corradini, Dylan Thurston, and Jamie Tucker-Foltz, Models of Random Spanning Trees, arXiv:2407.20226 [math.CO], 2024.
Jamie Tucker-Foltz, Code to compute a(n) on GitHub.
EXAMPLE
a(3) = 2 because there are 2 orderings of the edges a, b, and c of K_3 that give the path {a, b}: (a, b, c) and (b, a, c).
PROG
(PARI)
E(p, m)={sum(k=0, m, sum(i=0, k, polcoef(p, i)*i!*(m-i)! )*x^k/(k!*(m-k)!))}
seq(n)={my(v=vector(n)); v[1]=1; for(n=2, n, my(p=sum(k=1, n-1, v[k]*v[n-k])); v[n]=E(intformal(p), binomial(n, 2))); vector(n, n, my(m=binomial(n, 2)); m!*polcoef(v[n], m))} \\ Andrew Howroyd, Jul 31 2024
CROSSREFS
KEYWORD
nonn
AUTHOR
Jamie Tucker-Foltz, Jul 02 2024
STATUS
approved