Total Number of Set Partitions/Examples/4

From ProofWiki
Jump to navigation Jump to search

Example of Total Number of Set Partitions

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

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


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 4\) \(=\) \(\ds B_4\)
\(\ds \) \(=\) \(\ds {4 \brace 1} + {4 \brace 2} + {4 \brace 3} + {4 \brace 4}\) Bell Number as Summation over Lower Index of Stirling Numbers of the Second Kind
\(\ds \) \(=\) \(\ds 1 + 7 + 6 + 1\) Definition of Stirling Numbers of the Second Kind
\(\ds \) \(=\) \(\ds 15\)

$\blacksquare$


Illustration

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

Then the partitions of $S$ are:

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


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Total_Number_of_Set_Partitions/Examples/4&oldid=461719"