Noncrossing Partitions

One of the many interpretations of the Catalan numbers is that they count the number of noncrossing partitions of the set .
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.
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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

Reference
[1] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge: Cambridge University Press, 1999 p. 226.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.