This site is supported by donations to The OEIS Foundation.

# Set partitions

A set partition is a partition of a set into nonempty disjoint subsets. For example, given the set
 {1, 7, 13, 19, 91, 133, 247, 1729}
, one possible partition is
 {{1}, {7, 13, 19}, {91, 133, 247, 1729}}
.

## Number of set partitions over set Np

Denote by

${\displaystyle N_{p}=\{1,2,\ldots ,p\}\,}$
the set of all positive integers no greater than
 p
, and by
${\displaystyle {\overline {p}}_{m}(k,N_{p})\,}$
the number of set partitions of a
 k
-set (
 k
elements set) in
 m
parts of size
 1, 2, ..., p
.

### Recurrence and initial conditions

${\displaystyle {\overline {p}}_{0}(0,N_{p})=1{\rm {~and~}}{\overline {p}}_{0}(k,N_{p})=0{\rm {~if~}}k>0;\,}$
${\displaystyle {\overline {p}}_{m}(k,N_{p})=0{\rm {~if~}}kmp;\,}$
${\displaystyle {\overline {p}}_{m}(k,N_{p})=\sum _{s=1}^{p}{\binom {k-1}{k-s}}~{\overline {p}}_{m-1}(k-s,N_{p}).\,}$

### Generating function

${\displaystyle \sum _{k=0}^{\infty }{\overline {p}}_{m}(k,N_{p})~{\frac {x^{k}}{k!}}={\frac {1}{m!}}\left(x+{\frac {x^{2}}{2!}}+\ldots +{\frac {x^{p}}{p!}}\right)^{m}\,}$

### Associated sequences

${\displaystyle {\overline {p}}(k,N_{p})=\sum _{m=0}^{\infty }{\overline {p}}_{m}(k,N_{p})\,}$
${\displaystyle {\overline {p}}_{m}(N_{p})=\sum _{k=0}^{\infty }{\overline {p}}_{m}(k,N_{p})\,}$

## Number of set partitions over set N2

### Table

Based on initals conditions and general recurrence for
 p = 2
, we have following formulas
${\displaystyle {\overline {p}}_{0}(0,N_{2})=1{\rm {~and~}}{\overline {p}}_{0}(k,N_{2})=0{\rm {~if~}}k>0;\,}$
${\displaystyle {\overline {p}}_{m}(k,N_{2})=0{\rm {~if~}}k2m;\,}$
${\displaystyle {\overline {p}}_{m}(k,N_{2})=\sum _{s=1}^{2}{\binom {k-1}{k-s}}~{\overline {p}}_{m-1}(k-s,N_{2})={\overline {p}}_{m-1}(k-1,N_{2})~+~(k-1)~{\overline {p}}_{m-1}(k-2,N_{2}).\,}$
m \ k 0 1 2 3 4 5 6 7 8 9 10 ...
 p̅m (N2 )
0 1 0 0 0 0 0 0 0 0 0 0 . 1
1 0 1 1 0 0 0 0 0 0 0 0 . 2
2 0 0 1 3 3 0 0 0 0 0 0 . 7
3 0 0 0 1 6 15 15 0 0 0 0 . 37
4 0 0 0 0 1 10 45 105 105 0 0 . 266
5 0 0 0 0 0 1 15 105 420 945 945 . 2431
... . . . . . . . . . . . . .
 p̅  (k, N2)
1 1 2 4 10 26 76 . .

### Explicit formula

${\displaystyle {\overline {p}}_{m}(k,N_{2})={\frac {k!}{(2m-k)!~(k-m)!~2^{k-m}}}\,}$

### Associated sequences

#### First sequence

${\displaystyle {\overline {p}}(k,N_{2})=\sum _{m=\lfloor k/2\rfloor }^{k}{\frac {k!}{(2m-k)!~(k-m)!~2^{k-m}}}\,}$
giving the sequence (Cf. A000085
 (k), k   ≥   0
)
 {1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, 211799312, 997313824, 4809701440, 23758664096, 119952692896, ...}

#### Second sequence

${\displaystyle {\overline {p}}_{m}(N_{2})=\sum _{k=m}^{2m}{\frac {k!}{(2m-k)!~(k-m)!~2^{k-m}}}\,}$
giving the sequence (Cf. A001515
 (m), m   ≥   0
)
 {1, 2, 7, 37, 266, 2431, 27007, 353522, 5329837, 90960751, 1733584106, 36496226977, 841146804577, 21065166341402, 569600638022431, 16539483668991901, ...}

## Number of set partitions over set N3

### Table

Based on initals conditions and general recurrence for
 p = 3
we have following formulas
${\displaystyle {\overline {p}}_{0}(0,N_{3})=1{\rm {~and~}}{\overline {p}}_{0}(k,N_{3})=0{\rm {~if~}}k>0;\,}$
${\displaystyle {\overline {p}}_{m}(k,N_{3})=0{\rm {~if~}}k3m;\,}$
${\displaystyle {\overline {p}}_{m}(k,N_{3})=\sum _{s=1}^{3}{\binom {k-1}{k-s}}~{\overline {p}}_{m-1}(k-s,N_{3})={\overline {p}}_{m-1}(k-1,N_{3})~+~(k-1)~{\overline {p}}_{m-1}(k-2,N_{3})~+~{\frac {1}{2}}~(k-1)(k-2)~{\overline {p}}_{m-1}(k-3,N_{3}).\,}$
m \ k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...
 p̅m (N3 )
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . 1
1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 . 3
2 0 0 1 3 7 10 10 0 0 0 0 0 0 0 0 0 . 31
3 0 0 0 1 6 25 75 175 280 280 0 0 0 0 0 0 . 842
4 0 0 0 0 1 10 65 315 1225 3780 9100 15400 15400 0 0 0 . 45296
5 0 0 0 0 0 1 15 140 980 5565 26145 102025 323400 800800 1401400 1401400 . 4061871
... . . . . . . . . . . . . .
 p̅  (k, N3)
1 1 2 5 14 46 . . .

### Explicit formula

${\displaystyle {\overline {p}}_{m}(k,N_{3})=\sum _{i=0}^{3m-k}{\frac {k!}{(m-i)!~(k+2i-3m)!~(3m-i-k)!~2^{k+i-2m}~3^{m-i}}}.\,}$

### Associated sequences

#### First sequence

${\displaystyle {\overline {p}}(k,N_{3})=\sum _{m=\lfloor k/3\rfloor }^{k}\sum _{i=0}^{3m-k}{\frac {k!}{(m-i)!~(k+2i-3m)!~(3m-i-k)!~2^{k+i-2m}~3^{m-i}}}.\,}$
giving the sequence (Cf. A001680
 (k), k   ≥   0
)
 {1, 1, 2, 5, 14, 46, 166, 652, 2780, 12644, 61136, 312676, 1680592, 9467680, 55704104, 341185496, 2170853456, 14314313872, 97620050080, 687418278544, ...}

#### Second sequence

${\displaystyle {\overline {p}}_{m}(N_{3})=\sum _{k=m}^{3m}\sum _{i=0}^{3m-k}{\frac {k!}{(m-i)!~(k+2i-3m)!~(3m-i-k)!~2^{k+i-2m}~3^{m-i}}}.\,}$
giving the sequence (Cf. A144416
 (m), m   ≥   0
)
 {1, 3, 31, 842, 45296, 4061871, 546809243, 103123135501, 25942945219747, 8394104851717686, 3395846808758759686, 1679398297627675722593, ...}

## Number of set partitions

The number of [unrestricted] set partitions is given by the Bell numbers (exponential numbers).

A000110 Bell or exponential numbers: number of ways to partition a set of
 n, n   ≥   0,
labeled elements.
 {1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, ...}