1088 CHAPTER 11 Further Topics in Algebra 11.6 Basics of Counting Theory ■ Fundamental Principle of Counting ■ Permutations ■ Combinations ■ Characteristics That Distinguish Permutations from Combinations Albany Baker Baker Baker Creswich Creswich Creswich Creswich Creswich Creswich Figure 13 Fundamental Principle of Counting Consider the following problem. If there are 3 roads from Albany to Baker and 2 roads from Baker to Creswich, in how many ways can one travel from Albany to Creswich by way of Baker? For each of the 3 roads from Albany to Baker, there are 2 different roads from Baker to Creswich. Hence, there are 3 # 2 = 6 different ways to make the trip, as shown in the tree diagram in Figure 13. Here, each choice of road is an example of an event. Two events are independent events if neither influences the outcome of the other. Fundamental Principle of Counting If n independent events occur, with m1 ways for event 1 to occur, m2 ways for event 2 to occur, . . . and mn ways for event n to occur, then there are m1 # m2 # P# mn different ways for all n events to occur. The opening example illustrates the fundamental principle of counting with independent events. EXAMPLE 1 Using the Fundamental Principle of Counting A restaurant offers a choice of 3 salads, 5 main dishes, and 2 desserts. Use the fundamental principle of counting to find the number of different 3-course meals that can be selected. SOLUTION Three independent events are involved: selecting a salad, selecting a main dish, and selecting a dessert. The first event can occur in 3 ways, the second event can occur in 5 ways, and the third event can occur in 2 ways. 3 # 5 # 2 = 30 possible meals S Now Try Exercise 7. EXAMPLE 2 Using the Fundamental Principle of Counting A teacher has 5 different books that he wishes to arrange in a row. How many different arrangements are possible? SOLUTION Five events are involved: selecting a book for the first spot, selecting a book for the second spot, and so on. For the first spot the teacher has 5 choices. Here the outcome of the first event does influence the outcome of the second event, because one book has already been chosen. Thus the teacher has 4 choices for the second spot. Continuing in this manner, there are 3 choices for the third spot, 2 for the fourth spot, and 1 for the fifth spot. We use the fundamental principle of counting. 5 # 4 # 3 # 2 # 1 = 120 different arrangements S Now Try Exercise 11.
RkJQdWJsaXNoZXIy NjM5ODQ=