|
| |
|
|
A165208
|
|
The number of maximal paths in the Bruhat graph for S_n.
|
|
0
| |
|
|
1, 1, 5, 210, 162482, 3431771334, 2675532842827606, 98099380263646542332472, 207159998877655913898903666460600, 29992398464230524512087152790819658487446680
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| The Bruhat graph on S_n is the directed graph with an edge connecting v to w whenever v and w differ by a transposition and w has more inversions than v. A maximal path in the Bruhat graph on S_n is one which goes from the identity element to the longest permutation [n,n-1,..., 2,1] written in one-line notation. Note, the Bruhat graph has more edges than the Hasse diagram for the Bruhat order. For example in S_3, [123] is connected to [321] in the Bruhat graph because they differ by a single transposition.
|
|
|
REFERENCES
| Anders Bjorner and Francesco Brenti, "Combinatorics of Coxeter Groups". Graduate Texts in Mathematics, 231. Springer, New York, 2005.
Francesco Brenti, "Lattice paths and Kazhdan-Lusztig polynomials" J. Amer. Math. Soc., 11 (1998), 229-259.
James Carrell, "The Bruhat graph of a Coxeter group, a conjecture of Deodhar, and rational smoothness of Schubert varieties". Proceedings of Symposia in Pure Math.}, 56 (1994), 53--61.
|
|
|
CROSSREFS
| Cf. A061710
Sequence in context: A006413 A055316 A203470 * A144796 A206457 A119657
Adjacent sequences: A165205 A165206 A165207 * A165209 A165210 A165211
|
|
|
KEYWORD
| hard,nonn
|
|
|
AUTHOR
| Sara C. Billey (billey(AT)uw.edu), Sep 07 2009
|
| |
|
|
