ThmDex – An index of mathematical definitions, results, and conjectures.
Result R1864 on D2913: Bell coefficient
Sum of Bell coefficients
Formulation 1
Let $X$ be a D17: Finite set such that
(i) \begin{equation} |X| = N \in \mathbb{N} \end{equation}
(ii) $\text{Part} X$ be the D2910: Set of proper set partitions for $X$
Then \begin{equation} | \text{Part} X | = \sum_{n = 0}^N {N \brace n} \end{equation}
Formulation 2
Let $X$ be a D17: Finite set such that
(i) $\text{Part} X$ be the D2910: Set of proper set partitions for $X$
Then \begin{equation} |\text{Part} X| = \sum_{n = 0}^{|X|} {|X| \brace n} \end{equation}
Proofs
Proof 0
Let $X$ be a D17: Finite set such that
(i) $\text{Part} X$ be the D2910: Set of proper set partitions for $X$
Suppose that $X$ has $N \in \{ 1, 2, 3, \ldots \}$ elements. We can write \begin{equation} \text{Part} X = \bigcup_{n = 0}^N \{ P \subseteq \mathcal{P}(X) : P \text{ partitions } X \text{ and } |P| = n \} \end{equation} The sets in the union are disjoint since each set consists of partitions of different sizes. Hence, applying result R1838: Cardinality of finite set union of finite sets yields \begin{equation} \begin{split} |\text{Part} X| & = \left| \bigcup_{n = 0}^N \{ P : P \text{ partitions } X \text{ and } |P| = n \} \right| \\ & = \sum_{n = 0}^N \left| \{ P : P \text{ partitions } X \text{ and } |P| = n \} \right| \\ & = \sum_{n = 0}^N {N \brace n} \end{split} \end{equation} This is the desired result. $\square$