Fundamental Principle of Counting

From ProofWiki
(Redirected from Sum Rule for Counting)
Jump to navigation Jump to search


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