Number of Elements in Partition
Jump to navigation
Jump to search
Theorem
Let $S$ be a set.
Let there be a partition on $S$ of $n$ subsets, each of which has $m$ elements.
Then:
- $\card S = n m$
Proof
Let the partition of $S$ be $S_1, S_2, \ldots, S_n$.
Then:
- $\forall k \in \set {1, 2, \ldots, n}: \card {S_k} = m$
By definition of multiplication:
- $\ds \sum_{k \mathop = 1}^n \card {S_k} = n m$
and the result follows from the Fundamental Principle of Counting.
$\blacksquare$
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 19$: Combinatorial Analysis: Theorem $19.1$