Partition Of A Set

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.

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 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 Human s 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 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 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'' 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 Partition s 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''₀ = 1,
''B''₁ = 1, ''B''₂ = 2, ''B''₃ = 5, ''B''₄ = 15, ''B''₅ = 52, ''B''₆ = 203.

The Exponential Generating Function for Bell numbers is

\sum_{n=0}^\inftyrac{B_n}{n!}z^n=e^{e^z-1}

; this equality is known as Dobinski's Formula . Bell numbers satisfy the Recursion

B_{n+1}=\sum_{k=0}^n {n\choose 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''th Catalan Number , given by

:

C_n={1 \over n+1}{2n \choose n}.

	CATEGORIES ABOUT PARTITION OF A SET

	combinatorics

	basic concepts in set theory

	set families

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

Information About

Partition Of A Set