[Previous] [Next] [Contents]

[ImplState=stable,TestState=stable,DocState=stable]

combinat::permutations::leequalBruhat -- Bruhat order on standard permutations

Introduction

Functions related to the Bruhat order on permutations.

Details

Method leequalBruhat: Test of the order relation of two permutations

Method bruhatInversions: list of inversions in the Bruhat order

Method predBruhat: list of the precedessors of a permutation

Method succBruhat: list of the successors of a permutation

Method smallerBruhat: list of the permutations smaller than a permutation

Method greaterBruhat: list of the permutations greater than a permutation

Example 1

To check whether a permutation is smaller than another thanks to the Bruhat order, you can call:

>> combinat::permutations::leequalBruhat([2,4,3,1],[3,4,2,1]);
     
                                   TRUE
        

You can ask for the inversions of a given permutation by:

>> combinat::permutations::bruhatInversions([6, 1, 4, 5, 2, 3])
     
         [{1, 2}, {1, 3}, {1, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}]
        

Applying those inversions to the previous permutation, you exactly get the permutations preceding it as you can check with

>> combinat::permutations::predBruhat([6, 1, 4, 5, 2, 3])
     
      [[1, 6, 4, 5, 2, 3], [4, 1, 6, 5, 2, 3], [5, 1, 4, 6, 2, 3],
      
         [6, 1, 2, 5, 4, 3], [6, 1, 3, 5, 2, 4], [6, 1, 4, 2, 5, 3],
      
         [6, 1, 4, 3, 2, 5]]
        

Now, you can compute the transitive ideal generated by the predecessor relation and get (on the previous example, the answer is one page long)

>> combinat::permutations::smallerBruhat([4, 1, 2, 3])
     
      [[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 4, 2, 3],
      
         [2, 1, 3, 4], [2, 1, 4, 3], [3, 1, 2, 4], [4, 1, 2, 3]]
        

What was done with the permutations preceding a given one or smaller than it, can also be performed by the permutations succeeding a given one or greater than it by:

>> combinat::permutations::succBruhat([6, 1, 4, 5, 2, 3]);
   combinat::permutations::greaterBruhat([4, 1, 2, 3])
     
      [[6, 4, 1, 5, 2, 3], [6, 2, 4, 5, 1, 3], [6, 1, 5, 4, 2, 3],
      
         [6, 1, 4, 5, 3, 2]]
      
      [[4, 3, 2, 1], [4, 3, 1, 2], [4, 2, 3, 1], [4, 2, 1, 3],
      
         [4, 1, 3, 2], [4, 1, 2, 3]]
        

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package