Section 8.2 – Methods of Enumeration 341 Section 8.2 Methods of Enumeration The ability to determine quantities in various scenarios—literally, counting—is important to mathematics and probability. The field devoted to this task is called combinatorics. We start with the Multiplication Principal. The Multiplication Principle and the Factorial The first example is meant to be strongly intuitive: Example 1: Suppose an ice cream parlor has 4 different kinds of cones and 5 flavors of ice cream. How many ways can an ice cream cone be assembled, with one scoop placed into one cone? Discussion: There are four choices of cone, and each of those cones could be filled with one of the five choices of ice cream. It is possible to list out all the pairings. Let a, b, c, d represent the cones and 1, 2, 3, 4, 5 represent the flavors: Flavor 1 2 3 4 5 Cone: a a1 a2 a3 a4 a5 b b1 b2 b3 b4 b5 c c1 c2 c3 c4 c5 d d1 d2 d3 d4 d5 Hence, there are 20 different ways to pair one scoop of ice cream with each cone. It was reasonable to multiply the number of choices together to determine the total number of combinations. This is the basis of the following principle: The Multiplication Principle (also known as the Fundamental Counting Principle): Given a scenario where a sequence of choices is to be made, then the total number of choices is the product of the individual number of choices. Comment: The sequences of choices are being made in conjunction with one another. That is, we make choice 1, and then choice 2, and then choice 3, so forth. The word conjunction is the logical connector “and”. The Multiplication Principle is very simple to use in practice. The best way to gain a feel for this principle is to work through plenty of examples. Example 2: At the same ice cream parlor as in the previous example, you want to add a topping, of which there are 6 choices available. How many possible ways can you assemble your ice cream treat (cone, flavor and topping)? Discussion. Multiply the number of choices together: 120654=××. There are 120 possible combinations of cone, flavor and topping. Section 8.2 – Methods of Enumeration 342 Example 3: A coin is flipped twice. How many outcomes are possible? Discussion. Each flip has 2 possibilities, hence there are 422=× possible outcomes. They form a set of outcomes: {HH, HT, TH, TT}. Example 4: A coin is flipped 10 times. How many outcomes are possible? Discussion. Proceeding as in the previous example, we have 2 multiplied by itself 10 times, or 024,1210= possible outcomes. The set itself is obviously too large to list. Example 5: An automobile’s license plate consists of three letters (A-Z) followed by three numerical digits (0-9). How many plates are possible if a) there are no restrictions (repetition is allowed)? b) all letters and numbers must be different (repetition is not allowed)? Discussion. In the first case (a) where there are no restrictions and repetition of the same letter or numeral is allowed, there are 000,576,17102633=⋅ possible license plates. We used exponential shorthand for the calculation. In the second case (b) where repetition is not allowed, we see that there are 000,232,118910242526=××××× possible plates. Example 6: A true-false exam has 8 questions, followed by 10 multiple-choice questions, each with four choices. How many ways can this test be filled? Discussion. For the true-false portion, there are 25628= ways to randomly answer the questions. For the multiple choice portion, there are 576,048,1410= ways to randomly answer the questions. Taken as a whole, we multiply the two results together: 456,435,26842108=⋅ possible ways to fill in the exam. The following example illustrates a case when an “or” option is to be considered. In such a case we add the two results: Example 7: Radio and television station call letters are a sequence of three or four letters, with the first letter being a W (for stations east of the Mississippi River) and K (for stations west of the Mississippi River). How many such call letter sequences are possible? Discussion. For three letters sequences, there are two choices for the first position (W or K), and 26 choices each for the remaining two positions, for a total of 352,126262=×× three-letter sequences. For four letter sequences, the total number possible is 152,352626262=×××. Because these form two distinct classes of possible call-letter sequences, the total number of 3-letter or 4-letter call sequences is the sum: We sum the two to obtain 36,504 possible three-letter or four-letter call sequences. Many special properties can be derived from the Multiplication Principal by detecting some common patterns. The next example illustrates the factorial.Section 8.2 – Methods of Enumeration 343 Example 8: How many ways can 5 books be arranged on a bookshelf? Discussion. There are 12012345=×××× ways to arrange 5 books on a bookshelf. The ordering of the books is relevant. This example suggests a useful generalization, the factorial: The factorial of a positive integer n is the product of all integers from 1 to n inclusive: nnn×−××××=)1(321! K, along with the special case 0! = 1. Descriptively, n-factorial is defined to be the number of unique orderings of n objects. Many of the smaller factorial quantities are easily memorized, and you should consider doing so in order to expedite some of your calculations. The following is a short list of the first few factorial vales, and some sample visual orderings: n Number of orderings Example: 1 1! = 1 A 2 2! = 12× = 2 AB, BA 3 3! = 123×× = 6 ABC, ACB, BAC, BCA, CAB, CBA. 4 4! = 1234××× = 24 ABCD, ABDC, ACBD, ACDB, ADBC, ADCB, BACD, BADC, BCAD, BCDA, BDAC, BDCA, CABD, CADB, CBAD, CBDA, CDAB, CDBA, DABC, DACB, DBAC, DBCA, DCAB, DCBA 5 5! = 12345×××× = 120 The reader is invited to list them all! Figure. The table lists the possible orderings for the first few n objects. It is apparent the ways to order n objects increases very quickly! The factorial merely formalizes one common technique of counting. We shall use it in the development of two common counting scenarios:
View Full Document
Unlocking...