- 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.*

### Look at other dictionaries:

**Ordered partition of a set**— In combinatorial mathematics, an ordered partition O of a set S is a sequence A1, A2, A3, ..., An of subsets of S, with union is S, which are non empty, and pairwise disjoint. This differs from a partition of a set, in that the order of the Ai… … Wikipedia**Partition (number theory)**— Young diagrams associated to the partitions of the positive integers 1 through 8. They are so arranged that images under the reflection about the main diagonal of the square are conjugate partitions. In number theory and combinatorics, a… … Wikipedia**Partition**— Generally, a partition is a splitting of something into parts. The term is used in a variety of senses: Law *Partition (law), to divide up a piece of land into separate portions representing the proportionate interests of the tenants. It may also … Wikipedia**partition**— partitionable, adj. partitionary, adj. partitioner, partitionist, n. partitionment, n. /pahr tish euhn, peuhr /, n. 1. a division into or distribution in portions or shares. 2. a separation, as of two or more things. 3. something that separates… … Universalium**Partition (1987 film)**— Partition is a film by award winning director Ken McMullen. [imdb name|0573427|Ken McMullen] The film is set in the turmoil surrounding the transfer of political power in British India from British to Indian hands and the partition of the… … Wikipedia**Partition**— (lat. partitio ‚Abschnitt, Teil‘), auch Partitionierung (‚Aufteilung‘), bezeichnet: die Landesteilung in der Politik in der Mengenlehre eine Unterteilung von Mengen, siehe Partition (Mengenlehre) die Unterteilung von Datenträgern, siehe Partition … Deutsch Wikipedia**partition**— [pär tish′ən] n. [ME particioune < L partitio] 1. a parting or being parted; division into parts; separation; apportionment 2. something that separates or divides, as an interior wall dividing one room from another 3. a part or section;… … English World dictionary**Partition function (statistical mechanics)**— For other uses, see Partition function (disambiguation). Partition function describe the statistical properties of a system in thermodynamic equilibrium. It is a function of temperature and other parameters, such as the volume enclosing a gas.… … Wikipedia**Partition regular**— In mathematics, the notion of partition regularity in combinatorics is one approach to explaining when a set system is quite large.Given a set X, a collection of subsets mathbb{S} subset mathcal{P}(X) is called partition regular if for any A in… … Wikipedia**Partition function (mathematics)**— The partition function or configuration integral, as used in probability theory, information science and dynamical systems, is an abstraction of the definition of a partition function in statistical mechanics. It is a special case of a… … Wikipedia