A061710 -id:A061710 - cp's OEIS frontend

A165208 The number of maximal paths in the Bruhat graph for S_n.

1, 1, 5, 210, 162482, 3431771334, 2675532842827606, 98099380263646542332472, 207159998877655913898903666460600, 29992398464230524512087152790819658487446680

Offset: 1

Sara Billey, Sep 07 2009

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.

Anders Bjorner and Francesco Brenti, "Combinatorics of Coxeter Groups". Graduate Texts in Mathematics, 231. Springer, New York, 2005.
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.

Francesco Brenti, Lattice paths and Kazhdan-Lusztig polynomials, J. Amer. Math. Soc., 11 (1998), 229-259.

Cf. A061710.

A384959 Number of chains in the Bruhat order of type A_n.

Original entry on oeis.org

4, 36, 4524, 15166380, 2010484649524, 14206021962108887860

Offset: 1

Dmitry I. Ignatov, Jun 13 2025

The number of chains in the Bruhat order of the Weyl group A_n (isomorphic to the symmetric group S_{n+1}).

A. Bjorner and F. Brenti, Combinatorics of Coxeter Groups, Springer, 2009, 27-64.

V. V. Deodhar, On Bruhat ordering and weight-lattice ordering for a Weyl group, Indagationes Mathematicae, vol. 81, 1 (1978), 423-435.
A. Postnikov and R. P. Stanley, Chains in the Bruhat order, J. Algebr. Comb., 29 (2009), 133-174.

Cf. A061710 (maximal chains), A000142 (the order size), A005130 (the size of Dedekind-MacNeille completion), A384061 (number of antichains).

cp's OEIS Frontend

A165208 The number of maximal paths in the Bruhat graph for S_n.

Views

Author

Keywords

Comments

References

Links

Crossrefs