Section 6.1 Counting*
We are going to be interested in measuring how likely certain events are to occur; for example, we might want to know the likelihood that a certain number is prime, or the likelihood that a certain process will detect a solution to a discrete log problem. In order to make these measurements rigorous, we need to establish the basics of counting (yes, you've traveled for more than a decade to this advanced material, and only now do you get to learn how to count).
You are probably familiar with the next concept, though perhaps have not ever seen it formalized. As a motivating example, suppose you are have three shirts to choose from and four pairs of pants. How many different outfits can you make? It should be clear that we have to multiply the number of options to get the correct answer of eight (each shirt could be combined with four different pairs of pants). That choices or options multiply is such a central fact of counting that we give it a name.
Theorem 6.1.1. The fundamental principle of counting.
\(m\)\(n\)\(mn\text{.}\)An immediate consequence of this principle is that (by mathematical induction) any number of experiments can be performed, and all of their possible outcomes can be multipled to get the total number of possible outcomes. That is, \(k\) experiments having \(n_k\) possible outcomes respectively will have a total of \(n_1 n_2 \ldots n_k\) total combined possible outcomes.
Counting is important because it underlies our intuitive understanding of what probability is: the likelihood of an event is the ratio of the number of ways that even can happen to the total number of possible results in an experiement. The probability of a flipped coin landing on heads is 1/2 because there is one way that a coin can land heads up out of two possible outcomes to a flip. The probability of drawing a face card (J, Q, K) from a deck of a card is 12/52 because there are 12 face cards and 52 total cards that could be drawn. Thus, counting the number of events and the total number of possible outcomes is necessary to develop a theory of probability.