cp's OEIS Frontend

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.

%I A374293 #24 Aug 07 2024 13:33:54
%S A374293 1,1,2,44,27120,882241920,2443792425984000,846533597741050576896000,
%T A374293 50571850611494440562578575851520000,
%U A374293 686805008584962439650318114385825747697664000000,2701735270674169239689693528384644314472371275610193920000000000,3819958423456547324072333722421751679308286064300212197312630212725309440000000000
%N 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.
%C A374293 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 A374293 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 A374293 Jamie Tucker-Foltz, <a href="/A374293/b374293.txt">Table of n, a(n) for n = 1..16</a>
%H A374293 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 A374293 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 A374293 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 A374293 (PARI)
%o A374293 E(p,m)={sum(k=0, m, sum(i=0, k, polcoef(p, i)*i!*(m-i)! )*x^k/(k!*(m-k)!))}
%o A374293 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 A374293 Cf. A052295, A253950.
%K A374293 nonn
%O A374293 1,3
%A A374293 _Jamie Tucker-Foltz_, Jul 02 2024