login
A374293
a(n)/binomial(n,2)! is the probability that the minimum spanning tree of the complete graph of n vertices with i.i.d. random edge weights is a specific path.
2
1, 1, 2, 44, 27120, 882241920, 2443792425984000, 846533597741050576896000, 50571850611494440562578575851520000, 686805008584962439650318114385825747697664000000, 2701735270674169239689693528384644314472371275610193920000000000, 3819958423456547324072333722421751679308286064300212197312630212725309440000000000
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
Sequence in context: A291808 A161745 A048566 * A321058 A342827 A264438
KEYWORD
nonn
AUTHOR
Jamie Tucker-Foltz, Jul 02 2024
STATUS
approved