A
partition of a set S is a set of non-empty, pairwise disjoint subsets of
S, called "parts" or "blocks", whose union is all of
S. Consider a finite set that is linearly ordered, or (equivalently, for purposes of this definition) arranged in a
cyclic order like the vertices of a regular
n-gon. No generality is lost by taking this set to be
S = { 1, ...,
n }. A
noncrossing partition of
S is a partition in which no two blocks "cross" each other, i.e., if
a and
b belong to one block and
x and
y to another, they are not arranged in the order
a x b y. If one draws an arch based at
a and
b, and another arch based at
x and
y, then the two arches cross each other if the order is
a x b y but not if it is
a x y b or
a b x y. In the latter two orders the partition { {
a,
b }, {
x,
y } } is noncrossing. Equivalently, if we label the vertices of a regular
n-gon with the numbers 1 through
n, the
convex hulls of different blocks of the partition are disjoint from each other, i.e., they also do not "cross" each other. The set of all non-crossing partitions of
S is denoted \text{NC}(S). There is an obvious order isomorphism between \text{NC}(S_1) and \text{NC}(S_2) for two finite sets S_1,S_2 with the same size. That is, \text{NC}(S) depends essentially only on the size of S and we denote by \text{NC}(n) the non-crossing partitions on
any set of size
n. ==Lattice structure==