# Noncrossing Partitions

Noncrossing Partitions

One of the many interpretations of the Catalan numbers is that they count the number of noncrossing partitions of the set .

C

n

[n]={1,2,…,n}

A partition of is a disjoint collection of sets whose union is ; often these subsets are called blocks. Two blocks and are crossing if they contain elements and such that . (These situations are not crossing: , .) A noncrossing partition is a partition with no crossing pair of blocks.

[n]

[n]

A

W

a,b∈A

x,y∈W

a<x<b<y

a<b<x<y

a<x<y<b

This Demonstration shows two figures related to noncrossing partitions: one in which points are arranged at the corners of a regular polygon, with line segments connecting members of the same block; and one in which points are arranged in a line, with arcs joining members of the same block.