login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #24 Aug 07 2024 13:33:54

%S 1,1,2,44,27120,882241920,2443792425984000,846533597741050576896000,

%T 50571850611494440562578575851520000,

%U 686805008584962439650318114385825747697664000000,2701735270674169239689693528384644314472371275610193920000000000,3819958423456547324072333722421751679308286064300212197312630212725309440000000000

%N 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.

%C 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.

%C 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.

%H Jamie Tucker-Foltz, <a href="/A374293/b374293.txt">Table of n, a(n) for n = 1..16</a>

%H Eric Babson, Moon Duchin, Annina Iseli, Pietro Poggi-Corradini, Dylan Thurston, and Jamie Tucker-Foltz, <a href="https://arxiv.org/abs/2407.20226">Models of Random Spanning Trees</a>, arXiv:2407.20226 [math.CO], 2024.

%H Jamie Tucker-Foltz, <a href="https://github.com/mggg/MST-Distribution/blob/main/internal_external.py">Code to compute a(n) on GitHub</a>.

%e 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).

%o (PARI)

%o E(p,m)={sum(k=0, m, sum(i=0, k, polcoef(p, i)*i!*(m-i)! )*x^k/(k!*(m-k)!))}

%o 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

%Y Cf. A052295, A253950.

%K nonn

%O 1,3

%A _Jamie Tucker-Foltz_, Jul 02 2024