There are no approved revisions of this page, so it may
not have been
reviewed.
This article needs more work.
Please help by expanding it!
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
the set of all
positive integers no greater than
, and by
the
number of set partitions of a
-set (
elements set) in
parts of size
.
Recurrence and initial conditions
Generating function
Associated sequences
Number of set partitions over set N2
Table
Based on initals conditions and general recurrence for
, we have following formulas
m \ k |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
... |
|
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 |
... |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
|
1 |
1 |
2 |
4 |
10 |
26 |
76 |
. |
. |
|
Explicit formula
Associated sequences
First sequence
giving the sequence (Cf.
A000085 )
-
{1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, 211799312, 997313824, 4809701440, 23758664096, 119952692896, ...} |
Second sequence
giving the sequence (Cf.
A001515 )
-
{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
we have following formulas
m \ k |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
... |
|
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 |
... |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
. |
|
1 |
1 |
2 |
5 |
14 |
46 |
. |
. |
. |
|
Explicit formula
Associated sequences
First sequence
giving the sequence (Cf.
A001680 )
-
{1, 1, 2, 5, 14, 46, 166, 652, 2780, 12644, 61136, 312676, 1680592, 9467680, 55704104, 341185496, 2170853456, 14314313872, 97620050080, 687418278544, ...} |
Second sequence
giving the sequence (Cf.
A144416 )
-
{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
labeled elements.
-
{1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, ...} |
See also