Total Number of Set Partitions/Examples/3

Example of Total Number of Set Partitions

Let $S$ be a set whose cardinality is $3$.

Then the number of partitions of $S$ is $5$.

Proof

Let $\map p n$ denote the cardinality of the set of partitions of a set whose cardinality is $n$.

From Total Number of Set Partitions, $\map p n$ is the $n$th Bell number $B_n$.

Thus:

\(\ds \map p 3\)

\(=\)

\(\ds B_3\)

\(\ds \)

\(=\)

\(\ds {3 \brace 1} + {3 \brace 2} + {3 \brace 3}\)

Bell Number as Summation over Lower Index of Stirling Numbers of the Second Kind

\(\ds \)

\(=\)

\(\ds 1 + 3 + 1\)

Definition of Stirling Numbers of the Second Kind

\(\ds \)

\(=\)

\(\ds 5\)

$\blacksquare$

Illustration

Let a set $S$ of cardinality $3$ be exemplified by $S = \set {a, b, c}$.

Then the partitions of $S$ are:

$\set {a, b, c}$

$\set {a, b \mid c}$

$\set {a, c \mid b}$

$\set {b, c \mid a}$

$\set {a \mid b \mid c}$

Sources

• 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): Chapter $1$: Sets and Logic: Exercise $16 \ \text{(ii)}$