Set partitions

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 N_p

Denote by

$N_{p}=\{1,2,\ldots ,p\}\,$

the set of all positive integers no greater than 

p

, and by

${\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

${\overline {p}}_{0}(0,N_{p})=1{\rm {~and~}}{\overline {p}}_{0}(k,N_{p})=0{\rm {~if~}}k>0;\,$

${\overline {p}}_{m}(k,N_{p})=0{\rm {~if~}}k<m{\rm {~and~}}k>mp;\,$

${\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

$\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

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

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

Number of set partitions over set N₂

Table

Based on initals conditions and general recurrence for 

p = 2

, we have following formulas

${\overline {p}}_{0}(0,N_{2})=1{\rm {~and~}}{\overline {p}}_{0}(k,N_{2})=0{\rm {~if~}}k>0;\,$

${\overline {p}}_{m}(k,N_{2})=0{\rm {~if~}}k<m{\rm {~and~}}k>2m;\,$

${\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

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

Associated sequences

First sequence

${\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

${\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 N₃

Table

Based on initals conditions and general recurrence for 

p = 3

we have following formulas

${\overline {p}}_{0}(0,N_{3})=1{\rm {~and~}}{\overline {p}}_{0}(k,N_{3})=0{\rm {~if~}}k>0;\,$

${\overline {p}}_{m}(k,N_{3})=0{\rm {~if~}}k<m{\rm {~and~}}k>3m;\,$

${\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

${\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

${\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

${\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, ...}

See also

• Sets
  • Set partitions
  • Restricted set partitions
  • Set compositions
  • Restricted set compositions

• Multisets
  • Multiset partitions
  • Restricted multiset partitions
  • Multiset compositions
  • Restricted multiset compositions