- Partition of a set
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 bothcollectively exhaustive andmutually exclusive with respect to the set being partitioned.**Definition**A partition of a set "X" is a set of

nonempty subset s of "X" such that every element "x" in "X" is in exactly one of these subsets.Equivalently, a set "P" of nonempty sets is a partition of "X" if

#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" arepairwise disjoint .)The elements of "P" are sometimes called the

**blocks**or**parts**of the partition.Brualdi, "pp". 44-45]**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-emptyproper subset "A" of a set "U", this "A" together with its complement is a partition of "U".

*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 (because it contains the empty set).

** { {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 allequivalence class es 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" if there exists a member of "P" which contains both "x" and "y". The notions of "equivalence relation" and "partition" are thus essentially equivalent.Schechter, "p". 54]**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 thisHasse diagram :**Noncrossing partitions**The lattice of

noncrossing partition s of a finite set has recently taken on importance because of its role infree 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 ofEric 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 exponential generating function for Bell numbers is

:$sum\_\{n=0\}^inftyfrac\{B\_n\}\{n!\}z^n=e^\{e^z-1\}.$

Bell numbers satisfy the

recursion $B\_\{n+1\}=sum\_\{k=0\}^n\; \{nchoose\; k\}B\_k.$The

Stirling number of the second kind "S"("n", "k") 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 :$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

:$\{n!\; over\; m\_1!m\_2!m\_3!cdots\; 1!^\{m\_1\}2!^\{m\_2\}3!^\{m\_3\}cdots\}.$

The number of

noncrossing partition s of a set of size "n" is the "n"thCatalan number , given by:$C\_n=\{1\; over\; n+1\}\{2n\; choose\; n\}.$

**ee also***

Data clustering

*Equivalence relation

*Exponential formula

*List of partition topics

*Partial equivalence relation **Notes****References***cite book |last= Brualdi |first= Richard A. |title= Introductory Combinatorics |edition= 4th edition |year= 2004 |publisher= Pearson Prentice Hall |isbn= 0131001191

*cite book |last= Schechter |first= Eric |title= Handbook of Analysis and Its Foundations |year= 1997 |publisher= Academic Press |isbn= 0126227608

*Wikimedia Foundation.
2010.*