Partition (mathematics): Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Richard Pinch
imported>Richard Pinch
(→‎Partition (set theory): mention Bell number)
Line 14: Line 14:
Partitions and [[equivalence relation]]s give the same data: the [[equivalence class]]es of an equivalence relation on a set ''X'' form a partition of the set ''X'', and a partition <math>\mathcal{P}</math> gives rise to an equivalence relation where two elements are equivalent if they are in the same part from <math>\mathcal{P}</math>.
Partitions and [[equivalence relation]]s give the same data: the [[equivalence class]]es of an equivalence relation on a set ''X'' form a partition of the set ''X'', and a partition <math>\mathcal{P}</math> gives rise to an equivalence relation where two elements are equivalent if they are in the same part from <math>\mathcal{P}</math>.


The number of partitions of a finite set of size ''n'' into ''k'' parts is given by a [[Stirling number]] of the second kind.
The number of partitions of a finite set of size ''n'' into ''k'' parts is given by a [[Stirling number]] of the second kind; the total number of partitions of a set of size ''n'' is given by the ''n''-th [[Bell number]].


==Partition (number theory)==
==Partition (number theory)==

Revision as of 12:07, 13 December 2008

In mathematics, partition refers to two related concepts, in set theory and number theory.

Partition (set theory)

A partition of a set X is a collection of non-empty subsets ("parts") of X such that every element of X is in exactly one of the subsets in .

Hence a three-element set {a,b,c} has 5 partitions:

  • {a,b,c}
  • {a,b}, {c}
  • {a,c}, {b}
  • {b,c}, {a}
  • {a}, {b}, {c}

Partitions and equivalence relations give the same data: the equivalence classes of an equivalence relation on a set X form a partition of the set X, and a partition gives rise to an equivalence relation where two elements are equivalent if they are in the same part from .

The number of partitions of a finite set of size n into k parts is given by a Stirling number of the second kind; the total number of partitions of a set of size n is given by the n-th Bell number.

Partition (number theory)

A partition of an integer n is an expression of n as a sum of positive integers ("parts"), with the order of the terms in the sum being disregarded.

Hence the number 3 has 3 partitions:

  • 3
  • 2+1
  • 1+1+1

The number of partitions of n is given by the partition function p(n).