Probability. Robert P. Dobrow

alt="k Subscript n"/> possible values for the th element, there are possible sequences.

      For instance, in tossing a coin three times, there are possible outcomes. Rolling a die four times gives possible rolls.

       Example 1.11 License plates in Minnesota are issued with three letters from A to Z followed by three digits from 0 to 9. If each license plate is equally likely, what is the probability that a random license plate starts with G-Z-N?The solution will be equal to the number of license plates that start with G-Z-N divided by the total number of license plates. By the multiplication principle, there are possible license plates.For the number of plates that start with G-Z-N, think of a six-element plate of the form G-Z-N---. For the three blanks, there are 10 possibilities. Thus, the desired probability is

       Example 1.12 A DNA strand is a long polymer string made up of four nucleotides—adenine, cytosine, guanine, and thymine. It can be thought of as a sequence of As, Cs, Gs, and Ts. DNA is structured as a double helix with two paired strands running in opposite directions on the chromosome. Nucleotides always pair the same way: A with T and C with G. A palindromic sequence is equal to its “reverse complement.” For instance, the sequences CACGTG and TAGCTA are palindromic sequences (with reverse complements GTGCAC and ATCGAT, respectively), but TACCAT is not (reverse complement is ATGGTA). Such sequences play a significant role in molecular biology.Suppose the nucleotides on a DNA strand of length six are generated in such a way so that all strands are equally likely. What is the probability that the DNA sequence is a palindromic sequence?By the multiplication principle, the number of DNA strands is because there are four possibilities for each site. A palindromic sequence of length six is completely determined by the first three sites. There are palindromic sequences. The desired probability is

       Example 1.13 Logan is taking four final exams next week. His studying was erratic and all scores A, B, C, D, and F are equally likely for each exam. What is the probability that Logan will get at least one A?Take complements (often an effective strategy for “at least” problems). The complementary event of getting at least one A is getting no A's. As outcomes are equally likely, by the multiplication principle there are exam outcomes with no A's (four grade choices for each of four exams). And there are possible outcomes in all. The desired probability is

      1.6.1 Permutations

      Given a set of distinct objects, a permutation is an ordering of the elements of the set. For the set , there are six permutations:

      How many permutations are there of an -element set? There are possibilities for the first element of the permutation, for the second, and so on. The result follows by the multiplication principle.

      COUNTING PERMUTATIONS

      There are permutations of an -element set.

      The factorial function grows very large very fast. In a classroom of 10 people with 10 chairs, there are 3,628,800 ways to seat the students. There are orderings of a standard deck of cards, which is “almost” as big as the number of atoms in the observable universe, which is estimated to be about

      Functions of the form , where is a constant, are said to exhibit exponential growth. The factorial function grows like , which is sometimes called super-exponential growth.

The factorial function is pervasive in discrete probability. A good approximation when is large is given by Stirling's approximation

(1.4)

      More precisely,

      We say that “is asymptotic to” the function

For first impressions, it looks like the right-hand side of Equation 1.4 is more complicated than the left. However, the right-hand side is made up of relatively simple, elementary functions, which makes it possible to obtain useful approximations of factorials. Modern computational methods swap to computing logarithms of factorials to handle large computations, so in practice, you will likely not need to employ this formula.

      How do we use permutations to solve problems? The following examples illustrate some applications.

       Example 1.14 Maria has three bookshelves in her dorm room and 15 books—5 are math books and 10 are novels. If each shelf holds exactly five books and books are placed randomly on the shelves (all orderings are equally likely), what is the probability that the bottom shelf contains all the math books?There