Noncrossing Partitions

points

3

partition

1

style

polygon

flat

One of the many interpretations of the Catalan numbers

C

n

is that they count the number of noncrossing partitions of the set

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

.

A partition of

[n]

is a disjoint collection of sets whose union is

[n]

; often these subsets are called blocks. Two blocks

A

and

W

are crossing if they contain elements

a,b∈A

and

x,y∈W

such that

a<x<b<y

. (These situations are not crossing:

a<b<x<y

,

a<x<y<b

.) A noncrossing partition is a partition with no crossing pair of blocks.

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.