← Back to the home page

Noncrossing partitions

A set partition of an nn element set into blocks B1,B2,...,BkB_1, B_2, ..., B_k is noncrossing if for any 4 elements 1a<b<c<dn1 \leq a < b < c < d \leq n satisfying a,cBi and b,dBja, c \in B_i \text{ and }b, d \in B_j, we have i=ji = j.

They are counted by Catalan numbers.

A000108 on the OEIS

Source

Wikipedia

Comments

Loading comments...