# Partition of a set

A partition of

*U*into 6 blocks:

a Venn diagram representation.

In mathematics, a **partition** of a set *X* is a division of *X* into non-overlapping "**parts**" or "**blocks**" or "**cells**" that cover all of *X*. More formally, these "cells" are both collectively exhaustive and mutually exclusive with respect to the set being partitioned.

## Contents

## Definition

A partition of a set *X* is a set of nonempty subsets of *X* such that every element *x* in *X* is in exactly one of these subsets.

Equivalently, a set *P* of subsets of *X*, is a partition of *X* if

- No element of
*P*is empty. (**NB**- some definitions do not require this) - The union of the elements of
*P*is equal to*X*. (We say the elements of*P**cover**X*.) - The intersection of any two elements of
*P*is empty. (We say the elements of*P*are pairwise disjoint.)

The elements of *P* are sometimes called the **blocks** of the partition.

## Examples

- Every singleton set {
*x*} has exactly one partition, namely { {*x*} }. - For any set
*X*,*P*= {*X*} is a partition of*X*. - The empty set has exactly one partition, namely one with no blocks.
- Forgetting momentarily about certain exotic cases, the set of all humans can be partitioned into two blocks: the males and the females.
- For any non-empty proper subset
*A*of a set*U*, then*A*together with its complement is a partition of*U*. - If we do not use axiom 1, then the above example generalizes so that any subset (empty or not) together with its complement is a partition.
- The set { 1, 2, 3 } has these five partitions.
- { {1}, {2}, {3} }, sometimes denoted by 1/2/3.
- { {1, 2}, {3} }, sometimes denoted by 12/3.
- { {1, 3}, {2} }, sometimes denoted by 13/2.
- { {1}, {2, 3} }, sometimes denoted by 1/23.
- { {1, 2, 3} }, sometimes denoted by 123.

- Note that
- { {}, {1,3}, {2} } is not a partition if we are using axiom 1 (because it contains the empty set); otherwise it is a a partition of {1, 2, 3}.
- { {1,2}, {2, 3} } is not a partition (of any set) because the element 2 is contained in more than one distinct subset.
- { {1}, {2} } is not a partition of {1, 2, 3} because none of its blocks contains 3; however, it is a partition of {1, 2}.

## Partitions and equivalence relations

If an equivalence relation is given on the set *X*, then the set of all equivalence classes forms a partition of *X*. Conversely, if a partition *P* is given on *X*, we can define an equivalence relation on *X* by writing *x* ~ *y* iff there exists a member of *P* which contains both *x* and *y*. The notions of "equivalence relation" and "partition" are thus essentially equivalent.

## Partial ordering of the lattice of partitions

Given two partitions π and ρ of a given set *X*, we say that π is *finer* than ρ, or, equivalently, that ρ is *coarser* than π, if π splits the set *X* into smaller blocks than ρ does, i.e. if every element of π is a subset of some element of ρ. In that case, one writes π ≤ ρ.

The relation of "being-finer-than" is a partial order on the set of all partitions of the set *X*, and indeed even a complete lattice. In case *n* = 4, the partial order of the set of all 15 partitions is depicted in this Hasse diagram:

## Noncrossing partitions

The lattice of noncrossing partitions of a finite set has recently taken on importance because of its role in free probability theory. These form a subset of the lattice of all partitions, but not a sublattice, since the join operations of the two lattices do not agree.

## The number of partitions

The Bell number *B*_{n}, named in honor of Eric Temple Bell, is the number of different partitions of a set with *n* elements. The first several Bell numbers are *B*_{0} = 1,
*B*_{1} = 1, *B*_{2} = 2, *B*_{3} = 5, *B*_{4} = 15, *B*_{5} = 52, *B*_{6} = 203.

The Stirling number *S*(*n*, *k*) of the second kind
is the number of partitions of a set of size *n* into *k* blocks.

The number of partitions of a set of size *n* corresponding to the integer partition

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=\underbrace{1+\cdots+1}_{m_1\ \mbox{terms}} +\underbrace{2+\cdots+2}_{m_2\ \mbox{terms}} +\underbrace{3+\cdots+3}_{m_3\ \mbox{terms}}+\cdots}**

of *n*, is the Faà di Bruno coefficient

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {n! \over m_1!m_2!m_3!\cdots 1!^{m_1}2!^{m_2}3!^{m_3}\cdots}.}**

The number of noncrossing partitions of a set of size *n* is the *n*th Catalan number, given by

**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C_n={1 \over n+1}{2n \choose n}.}**

## See also

de:Partition (Mengenlehre) es:Partición (matemáticas) fr:Partition (mathématiques) hu:Osztályfelbontás it:Partizione pl:Podział zbioru fi:Ositus