Partition of a set

# Partition of a set

Overview

Discussion
 Ask a question about 'Partition of a set' Start a new discussion about 'Partition of a set' Answer questions from other users Full Discussion Forum

Encyclopedia

In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X. More formally, these "cells" are both collectively exhaustive
Collectively exhaustive
In probability theory, a set of events is jointly or collectively exhaustive if at least one of the events must occur. For example, when rolling a six-sided die, the outcomes 1, 2, 3, 4, 5, and 6 are collectively exhaustive, because they encompass the entire range of possible outcomes.Another way...

and mutually exclusive
Mutually exclusive
In layman's terms, two events are mutually exclusive if they cannot occur at the same time. An example is tossing a coin once, which can result in either heads or tails, but not both....

with respect to the set being partitioned.

## Definition

A partition of a set X is a set of nonempty subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

s of X such that every element x in X is in exactly one of these subsets.

Equivalently, a set P is a partition of X if, and only if, it does not contain the empty set and:
1. The union
Union (set theory)
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets S_1, S_2, S_3, \dots , S_n\,\! gives a set S_1 \cup S_2 \cup S_3 \cup \dots \cup S_n.- Definition :...

of the elements of P is equal to X. (The elements of P are said to cover X.)
2. The intersection
Intersection (set theory)
In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....

of any two distinct elements of P is empty. (We say the elements of P are pairwise disjoint.)

In mathematical notation, these two conditions can be represented as
1.
2.

where is the empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...

. The elements of P are called the blocks, parts or cells of the partition.

## Examples

• Every singleton set {x} has exactly one partition, namely { {x} }.
• For any nonempty set X, P = {X} is a partition of X.
• For any non-empty proper subset A of a set U, this A together with its complement
Complement (set theory)
In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...

is a partition of U.
• The set { 1, 2, 3 } has these five partitions:
• { {1}, {2}, {3} }, or 1/2/3.
• { {1, 2}, {3} }, or 12/3.
• { {1, 3}, {2} }, or 13/2.
• { {1}, {2, 3} }, or 1/23.
• { {1, 2, 3} }, or 123 (in contexts where there will be no confusion with the number).
• The following are not partitions of { 1, 2, 3 }:
• { {}, {1,3}, {2} } is not a partition because one of its elements is the empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...

.
• { {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

For any equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...

on a set X, the set of its equivalence classes is a partition of X. Conversely, from any partition P of X, we can define an equivalence relation on X by setting x ~ y precisely when x and y are in the same part in P. Thus the notions of equivalence relation and partition are essentially equivalent.

## Refinement of partitions

Any partition α of a set X is a refinement of a partition ρ of X—and we say that α is finer than ρ and that ρ is coarser than α—if every element of α is a subset of some element of ρ. Informally, this means that α is a further fragmentation of ρ. In that case, it is written that αρ.

This finer-than relation on the set of partitions of X is a partial order
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...

(so the notation "≤" is appropriate); it is a complete lattice
Complete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...

. For the simple example of X = {1, 2, 3, 4}, the partition lattice has 15 elements and is depicted in the following Hasse diagram
Hasse diagram
In order theory, a branch of mathematics, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction...

.

Another example illustrates the refining of partitions from the perspective of equivalence relations. If D is the set of cards in a standard 52-card deck, the same-color-as relation on D – which can be denoted ~C – has two equivalence classes: the sets {red cards} and {black cards}. The 2-part partition corresponding to ~C has a refinement that yields the same-suit-as relation ~S, which has the four equivalence classes {spades}, {diamonds}, {hearts}, and {clubs}.

## Noncrossing partitions

A partition of the set N = {1, 2, ..., n} with corresponding equivalence relation ~ is noncrossing
Noncrossing partition
In combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of its application to the theory of free probability...

provided that there are no distinct numbers a, b, c, and d in N with a < b < c < d for which a ~ c and b ~ d.
The lattice of noncrossing partitions of a finite set has recently taken on importance because of its role in free probability
Free probability
Free probability is a mathematical theory that studies non-commutative random variables. The "freeness" or free independence property is the analogue of the classical notion of independence, and it is connected with free products....

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.

## Counting partitions

The total number of partitions of an n-element set is the Bell number Bn. The first several Bell numbers are B0 = 1,
B1 = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, and B6 = 203. Bell numbers satisfy the recursion
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

and have the exponential generating function
Generating function
In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general...

The number of partitions of an n-element set into exactly k nonempty parts is the Stirling number of the second kind S(n, k).

The number of noncrossing partition
Noncrossing partition
In combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of its application to the theory of free probability...

s of an n-element set is the Catalan number
Catalan number
In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involvingrecursively defined objects...

Cn, given by

• Data clustering
Data clustering
Cluster analysis or clustering is the task of assigning a set of objects into groups so that the objects in the same cluster are more similar to each other than to those in other clusters....

• Equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...

• Exponential formula
Exponential formula
In combinatorial mathematics, the exponential formula states that the exponential generating function for structures on finite sets is the exponential of the exponential generating function for connected structures.The exponential formula is a power-series version of a special case of Faà di...

• Faà di Bruno formula
• Lamination
Lamination (topology)
In topology, a branch of mathematics, a lamination is a :* "A topological space partitioned into subsets"* decoration of a manifold in which some subset of the manifold is partitioned into sheets of some lower dimension, and the sheets are locally parallel.Lamination of surface is a partition of...

• List of partition topics
• Partial equivalence relation
Partial equivalence relation
In mathematics, a partial equivalence relation R on a set X is a relation that is symmetric and transitive...

• Partition refinement
Partition refinement
In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual to the union-find data structure, which also...