# Non crossing set partitions

A set partition is noncrossing if whenever four elements $$a are such that $$a,c$$ are in the same block and $$b,d$$ are in the same block then $$a,b,c,d$$ are all in the same block.

Can I get a list of noncrossing set partitions.

With "Combinatorica" I can get ALL the set partitions (say of {1,2,3,4}) with the command SetPartitions[4].

What I want is this list without the element {{1,3},{2,4}} which is not noncrossing.

Needs["Combinatorica"]

ClearAll[nonCrossingSetPartitions]
nonCrossingSetPartitions =
DeleteCases[{___, {___, a_, ___, c_, ___}, ___, {___, b_, ___, d_, ___}, ___} /;
a < b < c < d] @* SetPartitions;

nonCrossingSetPartitions @ 4 // Column


nonCrossingSetPartitions @ 5 // Length


42

• There should be 42 noncrossing partitions of [5]. Commented Sep 22, 2020 at 20:05
• thank you @geoffrey. Updated with a fix.
– kglr
Commented Sep 22, 2020 at 21:07

I have a Mathematica package for generating Catalan objects on GitHub, so I have some recursive algorithm which generates what you want. Moreover, it has a nice graphical representation of these, and some operations on these, such as rotation.

Needs["CatalanObjects"]
Last /@ NonCrossingPartitions[4]


to get

{{{1, 2, 3, 4}}, {{3}, {1, 2, 4}}, {{2}, {1, 3, 4}}, {{1, 4}, {2,
3}}, {{2}, {3}, {1, 4}}, {{1}, {2, 3, 4}}, {{1}, {3}, {2, 4}}, {{1,
2}, {3, 4}}, {{1}, {2}, {3, 4}}, {{4}, {1, 2, 3}}, {{2}, {4}, {1,
3}}, {{1}, {4}, {2, 3}}, {{3}, {4}, {1, 2}}, {{1}, {2}, {3}, {4}}}


If you do not want everything in the package, it should be easy to extract the method.

• Useful package, did you ever implemented this? Commented Jul 14, 2022 at 8:19
• @matrix89 I usually use the subsets function for that. Commented Jul 14, 2022 at 13:12