Counting Principles

Combinatorial Methods

[Counting Principle]If the set $E$ contains $n$ elements and the set $F$ contains $m$ elements, there are $nm$ ways in which we can choose, first, and element of $E$ and then an element of $F$ .

[Generalized Counting Principle] Let $E_1,E_2,...,E_k$ be sets with $n_1,n_2,...,n_k$ elements, respectively. Then there are $n_1 \cdot n_2 \cdot ... \cdot n_k$ ways in which we can choose an element from each of the $E_i's$ .

We use the two above theorems for counting the number of ways to choose distinct elements of different sets.

Example:
Home many outcomes are there if we throw five dice?

Solution: Let $E_i$ be the set of all possible outcomes for the $i$ th die, so $E_i = \set{1,2,3,4,5,6}$ . The number of outcomes of throwing five die equals the number of ways we can chose an element from each of the $E_i$ . So we get number of outcomes is $6^5.$

Example:
When tossing four fair dice, what is the probability that at least one is 3?

Solution: If we let $A$ be the event of at least one 3, then $A^c$ is the event of no 3 in tossing four dice. $N(A^c)$ is the number of sample points of $A^c$ , so for each die there are 5 possibilities, so $N(A^c) = 5\cdot 5 \cdot 5 \cdot 5 = 5^4$ , the number of sample points $N = 6^4$ . We have that $p(A^c) = \frac{N(A^c)}{N} = \frac{5^4}{6^4}$ and from this we get, $p(A) = 1 - p(A^c) = 1 - \frac{5^4}{6^4} = 1 - \frac{625}{1296} = \frac{671}{1296} \approx .52$ .

Example:
When tossing four fair dice, what is the probability that exactly one is 3?

Solution: We will let $A$ be the event that there is exactly one 3. If we let $E_i$ be the sample space for the $i$ th dice. We need to realize that if one die is 3, none of the others can be, so if the first die is three, then there are $5\times 5\times 5 = 125$ arrangements of the other three dice that do not choose 3 and since there are 4 dice, there are $4 \times 125 = 500$ ways that only one three can occur. Further, there are $6\times 6 \times 6 \times 6 = 1296$ , so

$p(A) = \frac{500}{1296} \approx 0.3858.$

Example:[Birthday Problem] What is the probability that in a class of size 30, that at least two students have the same birthday? Assume birthrates are constant throughout the year and that each year has 365 days.\\

Solution: Since there are 365 possible birthdays for each of the 30 students, so the sample space has $365^{30}$ points. There are $365 \cdot 364 \cdot ... \cdot 365 - 29$ ways that no two of the students birthdays coincide. So we let $p(N)$ is the probability that no two students have the same birthday is

$p(N) = \frac{365 \cdot 364 \cdot ... \cdot 365 - 29}{365^{30}}$

and so the desired probability then is $1 - p(N) = 0.706.$

Theorem:
A set with $n$ elements has $2^n$ subsets.