[Previous] [Next] [Contents]

## `combinat::nonCrossingPartitions` -- non crossing set partitions

#### Introduction

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

#### Details

- A non crossing set partition of 1, 2, ..., n is a partition p of the set 1, 2, ..., n such that there is no x,y in one part of p and z,t in another part of p with x<z<y<t. For example, `[1,3,7], [2], [4,5], [6], [8,9]` is a non crossing set partition, but `[1,3], [2,4]` is not (take `x=1, y=3, z=2, t=4`).

- A non crossing set partition of 1, 2, ..., n is represented as a set of lists. Each list represents a part of the partition, with its elements in increasing order.

- Non crossing set partitions are in bijection with Dyck words (library `combinat::dyckWords`), and many other discrete classes.

#### 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

- `count(nonnegative integer n)`

- Returns the number of non crossing set partitions of size `n`.

#### Method generator: generator for non crossing set partitions

- `generator(nonnegative integer n)`

- Returns a generator for the non crossing set partitions of size `n`.

#### Method list: list of the non crossing set partitions

- `list(nonnegative integer n)`

- Returns the list of the non crossing set partitions of size `n`.

#### 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