Partition (mathematics): Difference between revisions
imported>Richard Pinch (new entry, just a start) |
imported>Richard Pinch (reference to counting) |
||
| Line 2: | Line 2: | ||
==Partition (set theory)== | ==Partition (set theory)== | ||
A ''partition'' of a set ''X'' is a collection <math>\mathcal{P}</math> of subsets of ''X'' such that every element of ''X'' is in exactly one of the subsets in <math>\mathcal{P}</math>. | A ''partition'' of a set ''X'' is a collection <math>\mathcal{P}</math> of non-empty subsets ("parts") of ''X'' such that every element of ''X'' is in exactly one of the subsets in <math>\mathcal{P}</math>. | ||
Hence a three-element set {''a'',''b'',''c''} has 5 partitions: | Hence a three-element set {''a'',''b'',''c''} has 5 partitions: | ||
| Line 11: | Line 11: | ||
*{''b'',''c''}, {''a''} | *{''b'',''c''}, {''a''} | ||
*{''a''}, {''b''}, {''c''} | *{''a''}, {''b''}, {''c''} | ||
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. | |||
==Partition (number theory)== | ==Partition (number theory)== | ||
A ''partition'' of an [[integer]] ''n'' is an expression of ''n'' as a sum of [[positive integer]]s, with the order of the terms in the sum being disregarded. | A ''partition'' of an [[integer]] ''n'' is an expression of ''n'' as a sum of [[positive integer]]s ("parts"), with the order of the terms in the sum being disregarded. | ||
Hence the number 3 has 3 partitions: | Hence the number 3 has 3 partitions: | ||
| Line 21: | Line 25: | ||
* 2+1 | * 2+1 | ||
* 1+1+1 | * 1+1+1 | ||
The number of partitions of ''n'' is given by the [[partition function]] ''p''(''n''). | |||
Revision as of 05:30, 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.
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).