# 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]. – geoffrey Sep 22 '20 at 20:05
• thank you @geoffrey. Updated with a fix. – kglr Sep 22 '20 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.