Partition (mathematics)

| Main Article
| Discussion
| Related Articles  [?]
| Bibliography  [?]
| External Links  [?]
| Citable Version  [?]

|
|
|
|
|
|
|
|

This editable Main Article is under development and subject to a disclaimer.

[edit intro]

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

## Contents

* 1 Partition (set theory)
* 1.1 Bell numbers
* 2 Partition (number theory)
* 3 References

## Partition (set theory)[edit]

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[edit]

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

Bn=∑k=0n−1(m−1k)Bk.

They have an exponential generating function

eex−1=∑n=0∞Bnn!xn.

Asymptotically,

Bn∼n!2πW2(n)eW(n)eeW(n)−1Wn(n),

where W denotes the Lambert W function.

## Partition (number theory)[edit]

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[edit]

* Chen Chuan-Chong; Koh Khee-Meng (1992). Principles and Techniques of Combinatorics. World Scientific. ISBN 981-02-1139-2.