Proof of the Multiplication Principle
The Multiplication Principle
Two activities \(A_1\) and \(A_2\) can be performed in \(n_1\) and \(n_2\) different ways, respectively. The total number of ways in which \(A_1\) followed by \(A_2\) can be performed is \[n_{1} \times n_{2}.\]
(Rolf, 2005 p. 443)
Proof:
Denote the outcomes of the first activity (\(A_1\)) by \(a_1, \dots , a_m\) and the outcomes of the second activity (\(A_2\)) by \(b_1, \dots , b_n\). The outcomes for the two experiments are the ordered pairs \((a_i , b_j )\). These pairs can be exhibited as the entries of an \(m \times n\) rectangular array, in which the pair \((a_i , b_j )\) is in the \(i^{th}\) row and the \(j^{th}\) column. There are \(m \cdot n\) entries in this array. \( \blacksquare \)
(Rice, 1995, p. 8)
Additional Permutation Formula
Permutation Formula 2
Using the formula given in Mathematical Statistics and Data Analysis by Rice and then multiplying by one we get the following formula: \[ n(n - 1)(n - 2) \cdots (n - r + 1) \cdot \frac{(n-r)!}{(n-r)!} = \frac{n(n - 1)(n - 2) \cdots (n - r + 1)(n-r)!}{(n-r)!} \\ = \frac{n!}{(n-r)!} \]
This formula is often easier to understand and use.
Permutations and Combinations
Permutations count the number of ways we can select a sequence of objects from the same set where the order we pick them matters and combinations count the number of ways we can select a sequence of objects from the same set where order doesn't matter. Looking at their formulas, we can see the relation this way:
Relationship between Permutations and Combinations
If \( r \) elements are to be collected or arranged from a set of \( n \) elements, then the number of combinations of \( n \) elements taken \( r \) at a time, \( \binom{n}{r} \), related to the number of permutations of \( n \) elements taken \( r \) at a time, P(n,r), according to their equations is \[ \binom{n}{r} = \frac{n!}{(n-r)!r!} = \frac{P(n,r)}{r!}. \]
Thus the number combinations is inversely proportional to the number of permutations by the factor \( \frac{1}{r!} \).
Adapted from: Illinois State University Mathematics Department