Partition of a set

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 both collectively exhaustive and mutually exclusive with respect to the set being partitioned.

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 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" are pairwise 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-empty proper 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 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" 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 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 exponential generating function for Bell numbers is

:$sum_\left\{n=0\right\}^inftyfrac\left\{B_n\right\}\left\{n!\right\}z^n=e^\left\{e^z-1\right\}.$

Bell numbers satisfy the recursion $B_\left\{n+1\right\}=sum_\left\{k=0\right\}^n \left\{nchoose k\right\}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\left\{1+cdots+1\right\}_\left\{m_1 mbox\left\{terms+underbrace\left\{2+cdots+2\right\}_\left\{m_2 mbox\left\{terms+underbrace\left\{3+cdots+3\right\}_\left\{m_3 mbox\left\{terms+cdots$

of "n" is the Faà di Bruno coefficient

:$\left\{n! over m_1!m_2!m_3!cdots 1!^\left\{m_1\right\}2!^\left\{m_2\right\}3!^\left\{m_3\right\}cdots\right\}.$

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

:$C_n=\left\{1 over n+1\right\}\left\{2n choose n\right\}.$

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