|
|
A340398
|
|
Number of spanning trees in the Bruhat graph of the symmetric group.
|
|
0
|
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|