Partition (mathematics): Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Richard Pinch
(new entry, just a start)
 
mNo edit summary
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{subpages}}
In [[mathematics]], '''partition''' refers to two related concepts, in [[set theory]] and [[number theory]].
In [[mathematics]], '''partition''' refers to two related concepts, in [[set theory]] and [[number theory]].
==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 13:
*{''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;
===Bell numbers===
The total number of partitions of a set of size ''n'' is given by the ''n''-th '''Bell number''', denoted ''B''<sub>''n''</sub>.  These may be obtained by the [[recurrence relation]]
:<math>B_n=\sum_{k=0}^{n-1} \binom{m-1}{k} B_k .</math>
They have an [[exponential generating function]]
:<math> e^{e^x-1} = \sum_{n=0}^\infty \frac{B_n}{n!} x^n . </math>
Asymptotically,
:<math> B_n \sim \frac{n!}{\sqrt{2\pi W^2(n)e^{W(n)}}}\frac{e^{e^{W(n)}-1}}{W^n(n)},</math>
where ''W'' denotes the [[Lambert W function]].


==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 42:
* 2+1
* 2+1
* 1+1+1
* 1+1+1
The number of partitions of ''n'' is given by the [[partition function (number theory)|partition function]] ''p''(''n'').
==References==
* {{cite book | author=Chen Chuan-Chong | coauthors=Koh Khee-Meng | title=Principles and Techniques of Combinatorics | publisher=[[World Scientific]] | year=1992 | isbn=981-02-1139-2 }}[[Category:Suggestion Bot Tag]]

Latest revision as of 17:00, 1 October 2024

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

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;

Bell numbers

The total number of partitions of a set of size n is given by the n-th Bell number, denoted Bn. These may be obtained by the recurrence relation

They have an exponential generating function

Asymptotically,

where W denotes the Lambert W function.

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).

References