cp's OEIS Frontend

A340398 Number of spanning trees in the Bruhat graph of the symmetric group.

%I A340398 #16 Feb 16 2025 08:34:01
%S A340398 1,1,81,22799473113563136
%N A340398 Number of spanning trees in the Bruhat graph of the symmetric group.
%C A340398 The Bruhat graph of the symmetric group S_n has the set of all permutations on n elements as the vertex set and two permutations pi and sigma are connected with an edge if pi sigma^{-1} is a transposition.
%H A340398 R. Ehrenborg, <a href="https://doi.org/10.1016/j.aam.2020.102150">The number of spanning trees of the Bruhat graph</a>, Adv. in Appl. Math. 125 (2021), 102150.
%H A340398 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SpanningTree.html">Spanning Tree</a>
%H A340398 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TranspositionGraph.html">Transposition Graph</a>
%F A340398 a(n) = (1/n!) * Product_{lambda} (n*(n-1)/2 - Sum_{(i,j) in lambda} (j-i))^{f_{lambda}^2} where the product ranges over all integer partition lambda of n different from n, and f_{lambda} is the number of standard Young tableaux of shape lambda (see sequence A117506). Furthermore, the partitions are also viewed as their Ferrers shape, for instance, the partition 31 corresponds to the pairs (1,1), (1,2), (1,3) and (2,1).
%e A340398 For n=3 the number of spanning trees is 81 since the graph is the complete bipartite graph K_{3,3}.
%e A340398 For n=4, the following calculation demonstrates the formula:
%e A340398   31: 6 - (1-1) - (2-1) - (3-1) - (1-2) = 4;
%e A340398   22: 6 - (1-1) - (2-1) - (1-2) - (2-2) = 6;
%e A340398   211: 6 - (1-1) - (2-1) - (1-2) - (1-3) = 8;
%e A340398   1111: 6 - (1-1) - (1-2) - (1-3) - (1-4) = 12.
%e A340398 Hence the number of spanning trees is given by (1/4!) * 4^9 * 6^4 * 8^9 * 12^1 = 2^48 * 3^4 = 22799473113563136.
%Y A340398 Cf. A117506.
%K A340398 nonn
%O A340398 1,3
%A A340398 _Richard Ehrenborg_, Jan 06 2021