This is an old revision of the document!

Partition of a set

Definition

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

$\pi=\{V_1,\dots,V_n\},$

where $V_i\subset S$ , $V_i\neq\emptyset$ , and $V_i\cap V_j=\emptyset$ for any $i,j=1,\dots,n$ , $i\neq j$ . The subsets $V_i$ are called blocks of the partition $\pi$ .

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 $\pi=\{V_i\}_{i=1}^n$ is a partition of $S$ , then $(|V_i|)_{i=1}^n$ is a partition of $|S|$ .

Often we consider the set $S$ to be a totally ordered set. In this case, we can define the notion of a non-crossing partition. A partition $\pi=\{V_i\}_{i=1}^n$ of a totally ordered set $S$ is called non-crossing if for every four elements $a<b<c<d$ of $S$ having $a,c\in V_i$ and $b,d\in V_j$ implies $i=j$ . The name non-crossing is motivated by the graphical representation of such partitions (see below).

User Tools

Site Tools

Partition of a set

Definition

Page Tools