Let be a finite set. A partition of is a decomposition of into disjoint non-empty subsets. That is

where , , and for any , . The subsets are called blocks of the partition .

The set of all partitions of is denoted . In combinatorics, we usually take the canonical choice , for which we denote . When using partitions to build diagramatical categories (such as the category of all partitions), we consider partitions of a set and denote .

Partition of a set should not be confused with a partition of a number. Any partition of a set induces a partition of a number if we remember only the sizes of the sets. Indeed, if is a partition of , then is a partition of .

Often we consider the set to be a totally ordered set. In this case, we can define the notion of a non-crossing partition. A partition of a totally ordered set is called non-crossing if for every four elements of having and implies . The name non-crossing is motivated by the graphical representation of such partitions (see below).

We can represent elements , that is, partitions of a set as diagrams as follows. Put points on one line representing the elements of the set . For each block connect all the points representing elements of by a node.

For example, consider and a partition . This can be represented by the following diagram

If we draw all the nodes above the points (equivalently all the nodes bellow the points), we can characterize the non-crossing partitions using the graphical representation. A partition is non-crossing if and only if the lines corresponding to different blocks do not cross.

As an example, we see that the partition above is not non-crossing. Indeed, we have the sequence 2<3<5<6, where the points 2 and 5 belong to the first block and the points 3 and 6 belong to the second block. And indeed, in the graphical representation, the lines corresponding to the first and second block must cross each other.