Partition of a set - Citizendia

A partition of a set into 6 parts: an Euler diagram representation. Syllogism-Set-Diagramsjpg|thumb|Examples of small Venn diagrams with shaded regions representing Empty sets that are easily transformed into Euler diagrams

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. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and More formally, these "cells" are both collectively exhaustive and mutually exclusive with respect to the set being partitioned. In Probability theory, a set of events is collectively exhaustive if at least one of the events must occur In simple terms two events are mutually exclusive if they cannot occur at the same time (i

1 Definition
2 Examples
3 Partitions and equivalence relations
4 Partial ordering of the lattice of partitions
5 Noncrossing partitions
6 The number of partitions
7 See also
8 Notes
9 References

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. In Mathematics, and more specifically Set theory, the empty set is the unique set having no ( Zero) members

Equivalently, a set P of nonempty sets is a partition of X if

The union of the elements of P is equal to X. In Set theory, the term Union (denoted as ∪ refers to a set operation used in the convergence of set elements to form a resultant set containing the elements of both sets (We say the elements of P cover X. )
The intersection of any two elements of P is empty. In Mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently (We say the elements of P are pairwise disjoint. In Mathematics, two sets are said to be disjoint if they have no element in common )

The elements of P are sometimes called the blocks or parts of the partition. ^[1]

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. In Discrete mathematics and predominantly in Set theory, a complement is a concept used in comparisons of sets to refer to the unique values of one set in relation
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. In Mathematics, an equivalence relation is a Binary relation between two elements of a set which groups them together as being "equivalent" In Mathematics, given a set X and an Equivalence relation ~ on X, the equivalence class of an element a in 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. ^[2]

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 Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement In Mathematics, a complete lattice is a Partially ordered set in which all subsets have both a Supremum (join and an Infimum (meet 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. In the mathematical discipline known as Order theory, a Hasse diagram (ˈhɑːsə HAHS uh) named after Helmut Hasse (1898&ndash1979 is a In Combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of (among other things its application to the theory of Free probability Free probability is a mathematical theory which studies Non-commutative Random variables The "freeness" property is the analogue of the classical 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. In combinatorial Mathematics, the n th Bell number, named in honor of Eric Temple Bell, is the number of partitions of a set Eric Temple Bell ( February 7 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\frac{B_n}{n!}z^n=e^{e^z-1}.$

Bell numbers satisfy the recursion $B_{n+1}=\sum_{k=0}^n {n\choose k}B_k$ . In Mathematics a generating function is a Formal power series whose coefficients encode information about a Sequence a n Recursion, in Mathematics and Computer science, is a method of defining functions in which the function being defined is applied within its own definition

The Stirling number of the second kind S(n, k) is the number of partitions of a set of size n into k blocks. In Mathematics, Stirling numbers of the second kind, together with Stirling numbers of the first kind, are one of the two types of Stirling numbers They

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 partitions of a set of size n is the nth Catalan number, given by

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

Notes

^ Brualdi, pp. In Number theory, a partition of a positive Integer n is a way of writing n as a Sum of positive integers Faà di Bruno's formula is an identity in Mathematics generalizing the Chain rule to higher derivatives named in honor of Francesco Faà di Bruno (1825&ndash1888 In Combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of (among other things its application to the theory of Free probability In combinatorial mathematics, the Catalan numbers form a Sequence of Natural numbers that occur in various Counting problems often involving Clustering is the classification of objects into different groups or more precisely the partitioning of a Data set into Subsets (clusters In Mathematics, an equivalence relation is a Binary relation between two elements of a set which groups them together as being "equivalent" In combinatorial Mathematics, the exponential formula (called the polymer expansion in physics states that the exponential generating function for structures In Mathematics, a partition may be a Partition of a set or an Ordered partition of a set or a Partition of a graph In Mathematics, a partial equivalence relation (often abbreviated as PER) R on a set X is a relation which is symmetric 44-45
^ Schechter, p. 54

References

Brualdi, Richard A. (2004). Introductory Combinatorics, 4th edition, Pearson Prentice Hall. ISBN 0131001191.
Schechter, Eric (1997). Handbook of Analysis and Its Foundations. Academic Press. ISBN 0126227608.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents