The Basic Principle of Counting 計算的基本原理

The Basic Principle of Counting
Suppose that two experiments are to be performed. Then if experiment 1 can result in any one of m possible outcomes and if, for each outcome of experiment 1, there are n possible outcomes of experiment 2, then together there are mn possible outcomes of the two experiments.
Proof of the Basic Principle:
The basic principle may be provied by enumerating all the possible outcomes of the two experiments as follows:

where we say that the outcomes is (i,j) if experiment 1 results in its ith possible outcome and experiment 2 then results in the jth of its possible outcomes. Hence the set of possible outcomes consists of m rows, each row containing n elements, which proves the result.

Example
A small community consists of 10 women, each of whom has 3 children. If one woman and one of her children are to be chosen as mother and child of the year, how many different choices are possible?
Solution:
By regarding the choice of the woman as the outcome of the first experiment and the subsequent choice of one of her children as the outcome of he second experiment, we see, from the basic principle, that there are possible choices.