Fundamental Principle of Counting
Theorem
Let $A$ be a finite set.
Let $\sequence {B_n}$ be a sequence of distinct finite subsets of $A$ which form a partition of $A$.
Let $p_k = \size {B_k}$ for each $k \in \closedint 1 n$.
Then:
- $\ds \size A = \sum_{k \mathop = 1}^n p_k$
That is, the sum of the numbers of elements in the subsets of a partition of a set is equal to the total number of elements in the set.
Proof
Let $r_0 = 0$, and let:
- $\ds \forall k \in \closedint 1 n: r_k = \sum_{j \mathop = 1}^k {p_j}$
Then:
- $r_{k - 1} + p_k = r_k$
so:
- $r_{k - 1} < r_k$.
Thus by Isomorphism to Closed Interval, $\closedint {r_{k - 1} } {r_k}$ has $r_k - r_{k - 1} = p_k$ elements.
As a consequence, there exists a bijection $\sigma_k: B_k \to \closedint {r_{k - 1} } {r_k}$ for each $k \in \closedint 1 n$.
Let $\sigma: A \to \N$ be the mapping that satisfies:
- $\forall x \in B_k: \forall k \in \N: \map \sigma x = \map {\sigma_k} x$
By Strictly Increasing Sequence on Ordered Set, $\sequence {r_k}_{0 \mathop \le k \mathop \le n}$ is a strictly increasing sequence of natural numbers.
Thus by Strictly Increasing Sequence induces Partition, $\sigma: A \to \closedint 1 {r_n}$ is a bijection.
By Isomorphism to Closed Interval, $\closedint 1 {r_n}$ has $r_n$ elements.
Hence the result.
$\blacksquare$
Also known as
The Fundamental Principle of Counting is also known as:
- the Addition Principle
- the Sum Rule for Counting.
Also see
Sources
- 1965: J.A. Green: Sets and Groups ... (previous) ... (next): $\S 2.3$. Partitions
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 18$: Induced $N$-ary Operations: Theorem $18.4$
- 2007: Alan Tucker: Applied Combinatorics (5th ed.)
- 2008: David Joyner: Adventures in Group Theory (2nd ed.) ... (previous) ... (next): Chapter $2$: 'And you do addition?': $\S 2.4$: Counting and mathematical induction: Theorem $2.4.1$