The Counting Principle

The counting principle is the guiding rule for computing the number of elements in a cartesian product. Suppose that S and T are finite sets with m and n elements, respectively. The cartesian product of S and T is given by

$S \times T = \{ (x, y) | x \in S \wedge y \in T \} .$

The number of elements in the cartesian product S x T is equal to mn. Note that the total number of outcomes does not depend of the order in which the experiments are realized.

Example: Consider an experiment consisting of flipping a coin and rolling a die. There are two possibilities for the coin, heads or tails, and the die has six sides. The total number of outcomes for this experiment is 2 x 6 = 12. That is, there are twelve outcomes for the roll of a die followed by the toss of a coin: 1H, 1T, 2H, 2T, 3H, 3T, 4H, 4T, 5H, 5T, 6H, 6T.

The counting principle can be extended to compute the number of elements in the cartesian product of multiple sets. Consider the finite sets $S_1, S_2, \ldots, S_r$ and their cartesian product

$S_1 \times S_2 \times \cdots \times S_r = \left\{ (s_1, s_2, \ldots, s_r) | s_p \in S_p \right\} .$

If we denote the cardinality of $S p$ by $n p = | S p | , then the number of distinct ordered r-tuples of the form$ $(s_1, s_2, \ldots, s_r)$ is $n = n_1 n_2 \cdots n_r$ .

Example - Sampling with Replacement and Ordering: An urn contains n balls numbered 1 through n. A ball is drawn from the urn, and its number is recorded on an ordered list. The ball is then replaced in the urn. This procedure is repeated k times. We wish to compute the number of possible sequences that results from this experiment. There are k drawings and n possibilities per drawing. Using the counting principle, we conclude that the number of distinct sequences is $n k$ .

Example: The power set of S, denoted by $2 S$ , is the set of all subsets of S. In set theory, $2 S$ represents the set of all functions from S to {0, 1}. By identifying a function in $2 S$ with the corresponding preimage of one, we obtain a bijection between $2 S$ and the subsets of S. In particular, each function in $2 S$ is the characteristic function of a subset of S.

Suppose that S is finite with n = |S| elements. For every element of S, a characteristic function in $2 S$ is either zero or one. There are therefore $2 n$ distinct characteristic functions from S to {0, 1}. Hence, the number of distinct subsets of S is given by $2 n$ .

Extracted from http://en.wikibooks.org/wiki/Probability. Reproduced under the GNU Free Documentation License

GMAT Tutorials