Chapter 3 Combinatorics Permutations Many problems in probability theory require that we count the number of ways that a particular event can occur. For this, we study the topics of permutations and combinations. We consider permutations in this section and combinations | Chapter 3 Combinatorics Permutations Many problems in probability theory require that we count the number of ways that a particular event can occur. For this we study the topics of permutations and combinations. We consider permutations in this section and combinations in the next section. Before discussing permutations it is useful to introduce a general counting technique that will enable us to solve a variety of counting problems including the problem of counting the number of possible permutations of n objects. Counting Problems Consider an experiment that takes place in several stages and is such that the number of outcomes m at the nth stage is independent of the outcomes of the previous stages. The number m may be different for different stages. We want to count the number of ways that the entire experiment can be carried out. Example You are eating at Emile s restaurant and the waiter informs you that you have a two choices for appetizers soup or juice b three for the main course a meat fish or vegetable dish and c two for dessert ice cream or cake. How many possible choices do you have for your complete meal We illustrate the possible meals by a tree diagram shown in Figure . Your menu is decided in three stages at each stage the number of possible choices does not depend on what is chosen in the previous stages two choices at the first stage three at the second and two at the third. From the tree diagram we see that the total number of choices is the product of the number of choices at each stage. In this examples we have 2 3 2 12 possible menus. Our menu example is an example of the following general counting technique. 75 76 CHAPTER 3. COMBINATORICS Figure Tree for your menu. cake cake cake ice cream cake ice cream cake ice cream cake ice cream ice cream ice cream A Counting Technique A task is to be carried out in a sequence of r stages. There are n1 ways to carry out the first stage for each of these n1 ways there are n2 ways to carry .
