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

1, 1, 81, 22799473113563136

Offset

1,3

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.

Links

Table of n, a(n) for n=1..4.

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

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

Example

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.

Crossrefs

Cf. A117506.

Sequence in context: A116268 A128838 A231484 * A347172 A347175 A352032

Adjacent sequences: A340395 A340396 A340397 * A340399 A340400 A340401

Keyword

nonn

Author

Richard Ehrenborg, Jan 06 2021

Status

approved