Non-crossing Partitions

One of the many interpretations of the Catalan numbers Cn is that they count the number of noncrossing partitions of the set {1, 2, ..., n}. A non-crossing partition is a partition in which lines joining members of the same subset do not intersect any lines joining members of another subset.

One representation of noncrossing partitions is one in which points are arranged at the corners of a regular polygon, with line segments connecting members of the same block.

Two points, two non-crossing partitions {{1, 2}}—joined by a line since they’re in the same subset—and {{1}, {2}}—not joined since they’re in different subsets:

2 points, 2 partitions

Three points, five non-crossing partitions ({{1, 2, 3}}, {{1,2},{3}}, {{1,3},{2}}, {{1},{2,3}}, and {{1},{2},{3}}):

3 points, 5 partitions

Four points, 14 non-crossing partitions:

4 points, 14 partitions

Five points, 42 non-crossing partitions:

5 points, 42 partitions

An equivalent representation is one in which points are arranged in a line, with arcs joining members of the same block.

Two points, two non-crossing partitions ({{1, 2}} and {{1}, {2}}, again):

2 points, 2 partitions

Three points, five non-crossing partitions ({{1, 2, 3}}, {{1,2},{3}}, {{1,3},{2}}, {{1},{2,3}}, and {{1},{2},{3}}):

3 points, 5 partitions

Four points, 14 non-crossing partitions:

4 points, 14 partitions

Five points, 42 non-crossing partitions:

5 points, 42 partitions

Copyright © 2012–2017 by Robert Dickau.

[ home ] || [ 2012-04-22 ]


www.robertdickau.com/noncrossingpartitions.html