A384062 -id:A384062 - cp's OEIS frontend

A384061 Number of antichains in the Bruhat order of type A_n.

3, 9, 250, 67595432

Offset: 1

Dmitry I. Ignatov, May 18 2025

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

			For n=1 the elements are 1 (identity) and s1, the order contains pair (1, s1). The antichains are {}, {1}, and {s1}.
For n=2 the line (Hasse) diagram is below.
       s1*s2*s1
        /   \
      s2*s1 s1*s2
       |  X  |
       s2    s1
        \   /
          1
The set of antichains is {{}, {1}, {s2}, {s2, s1}, {s1}, {s2*s1}, {s2*s1, s1*s2}, {s1*s2}, {s1*s2*s1}}.

A. Bjorner, 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.

Cf. A000142 (the order size), A005130 (the size of Dedekind-MacNeille completion), A384062.

A383875 Number of pairs in the Bruhat order of type A_n.

Original entry on oeis.org

1, 3, 19, 213, 3781, 98407, 3550919

Offset: 0

Dmitry I. Ignatov, May 18 2025

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

			For n=0, the only element is 1 (identity) so a(0)=1.
For n=1 the elements are 1 (identity) and s1. The order relation consists of pairs (1, 1), (1, s1), and (s1, s1). So a(1) = 3.
For n=2 the line (Hasse) diagram is below.
       s1*s2*s1
        /   \
      s2*s1 s1*s2
       |  X  |
       s2    s1
        \   /
          1
The order relation consists of the six reflexive pairs, the eight pairs shown in the diagram as edges, and the five pairs (1, s2*s1), (1, s1*s2), (1, s1*s2*s1), (s1, s1*s2*s1), and (s2, s1*s2*s1). So a(2) = 6+8+5 = 19.

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.

Cf. A000142 (the order size), A002538 (edges in the cover relation), A005130 (the size of Dedekind-MacNeille completion), A384061 (antichains), A384062 (maximal antichains).

a(0)=1 prepended by Sara Billey, Jul 02 2025

cp's OEIS Frontend

A384061 Number of antichains in the Bruhat order of type A_n.

Views

Author

Keywords

Comments

Examples

References

Crossrefs