Small Set Partitions

size of set n

4

number of blocks k

2



1

234

 

12

34

 

134

2

 

123

4

 

14

23

 

124

3

 

13

24



This Demonstration shows the partitions of the set

{1,2,3,...,n}

into

k

blocks, where

n

and

k

are small. For example, you could split

{1,2,3,4,5}

into the blocks

{2}

,

{1,5}

, and

{3,4}

. This is written compactly as

2

15

34

.

The number of ways of partitioning a set of

n

elements into

k

nonempty subsets (or blocks) is the Stirling number of the second kind,

(k)



n

. The total number of ways to partition a set into blocks is the Bell number

B

n

=

n

∑

k=1

(k)



n

.