combinat::nonCrossingPartitions
--
non crossing set partitions
The library combinat::nonCrossingPartitions
provides functions for non crossing set
partitions.
[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
).combinat::dyckWords
), and many other discrete
classes.
Cat::CombinatorialClass
The MuPAD domain used to represent non crossing set partitions: DOM_SET
count(nonnegative integer n)
n
.
generator(nonnegative integer n)
n
.
list(nonnegative integer n)
n
.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]}
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]}]
Ax::systemRep
MuPAD Combinat, an open source algebraic combinatorics package