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

1, 1, 81, 22799473113563136

Offset: 1

Author

Richard Ehrenborg, Jan 06 2021

Keywords

• nonn

Comments

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.

Examples

			For n=3 the number of spanning trees is 81 since the graph is the complete bipartite graph K_{3,3}.
For n=4, the following calculation demonstrates the formula:
  31: 6 - (1-1) - (2-1) - (3-1) - (1-2) = 4;
  22: 6 - (1-1) - (2-1) - (1-2) - (2-2) = 6;
  211: 6 - (1-1) - (2-1) - (1-2) - (1-3) = 8;
  1111: 6 - (1-1) - (1-2) - (1-3) - (1-4) = 12.
Hence the number of spanning trees is given by (1/4!) * 4^9 * 6^4 * 8^9 * 12^1 = 2^48 * 3^4 = 22799473113563136.
		

Links

• R. Ehrenborg, The number of spanning trees of the Bruhat graph, Adv. in Appl. Math. 125 (2021), 102150.
• Eric Weisstein's World of Mathematics, Spanning Tree
• Eric Weisstein's World of Mathematics, Transposition Graph

Crossrefs

Cf. A117506.

Formula

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