[Previous] [Next] [Contents]

combinat::nonCrossingPartitions -- non crossing set partitions

Introduction

The library combinat::nonCrossingPartitions provides functions for non crossing set partitions.

Details

Categories

Cat::CombinatorialClass

Entries

domtype

The MuPAD domain used to represent non crossing set partitions: DOM_SET

Method count: number of non crossing set partitions

Method generator: generator for non crossing set partitions

Method list: list of the non crossing set partitions

Example 1

There are 14 non crossing set partitions of size 4:

>> combinat::nonCrossingPartitions::count(4)
     
                                    14
        

Here is the list:

>> combinat::nonCrossingPartitions::list(4)
     
      [{[1], [2], [3], [4]}, {[1], [2], [3, 4]}, {[1], [4], [2, 3]},
       
         {[1], [3], [2, 4]}, {[1], [2, 3, 4]}, {[3], [4], [1, 2]},
       
         {[1, 2], [3, 4]}, {[2], [4], [1, 3]}, {[4], [1, 2, 3]},
       
         {[2], [3], [1, 4]}, {[2], [1, 3, 4]}, {[1, 4], [2, 3]},
       
         {[3], [1, 2, 4]}, {[1, 2, 3, 4]}]
        

To generate non crossing set partitions of a given size:

>> g:= combinat::nonCrossingPartitions::generator(3):
   g(); g(); g(); g(); g(); g()
     
                              {[1], [2], [3]}
       
                               {[1], [2, 3]}
       
                               {[3], [1, 2]}
       
                               {[2], [1, 3]}
       
                                {[1, 2, 3]}
       
                                   FAIL
        

Typically, this would be used as follows:

>> g := combinat::nonCrossingPartitions::generator(3):
   while (p := g()) <> FAIL do print(p): end:
     
                              {[1], [2], [3]}
      
                               {[1], [2, 3]}
      
                               {[3], [1, 2]}
      
                               {[2], [1, 3]}
      
                                {[1, 2, 3]}
        

Example 2

Non crossing set partitions implements the Biane bijection with Dyck words.

>> combinat::dyckWords::count(i) $ i = 1..6;
   combinat::nonCrossingPartitions::count(i) $ i = 1..6 
     
                           1, 2, 5, 14, 42, 132
      
                           1, 2, 5, 14, 42, 132
        

And here is a little list comparation:

>> map(combinat::dyckWords::list(3),
       combinat::dyckWords::toNonCrossingPartition);
   combinat::nonCrossingPartitions::list(3)
     
      [{[1, 2, 3]}, {[2], [1, 3]}, {[3], [1, 2]}, {[1], [2, 3]},
       
         {[1], [2], [3]}]
       
      [{[1], [2], [3]}, {[1], [2, 3]}, {[3], [1, 2]}, {[2], [1, 3]},
       
         {[1, 2, 3]}]
        

Super-Domain

Dom::BaseDomain

Axioms

Ax::systemRep

[Previous] [Next] [Contents]


MuPAD Combinat, an open source algebraic combinatorics package