Читать книгу Probability - Robert P. Dobrow - Страница 28

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 are ways to permute all the books on the shelves. There are ways to put the math books on the bottom shelf and ways to put the remaining novels on the other two shelves. Thus, by the multiplication principle, the desired probability is

 Example 1.15 A bag contains six Scrabble tiles with the letters A-D-M-N-O-R. You reach into the bag and take out tiles one at a time. What is the probability that you will spell the word R-A-N-D-O-M?How many possible words can be formed? All the letters are distinct and a “word” is a permutation of the set of six letters. There are possible words. Only one of them spells R-A-N-D-O-M, so the desired probability is

 Example 1.16 Scrabble continued. Change the previous example. After you pick a tile from the bag, write down that letter and then return the tile to the bag. So every time you reach into the bag, it contains the six original letters. What is the probability that you spell R-A-N-D-O-M now when drawing six tiles?With the change, there are possible words, and only one still spells R-A-N-D-O-M, so the desired probability is