Permutations and Combinations

Permutations and Combinations Permutation is the act of rearranging the order of a set of objects. The word comes fromLatin permutare, "to change".A combination is defined as all possible subsets, with repetition allowed, from a given set.For example, if we take all possible subsets from three objects, we obtain sixcombinations: ABC, ACB, BAC, BCA, CAB and CBA.Permutations and combinations are two different types of counting problems. Thedifference is that permutations are about selecting without replacement, and combinationsare about selecting with replacement. We'll now discuss how probabilities can be thought of as the likelihood that certain eventswill occur in a particular order, or as the likelihood of a certain group of events occurring. For example, I may have five people working for me on five different assignments. But Ineed to place those people in those five different assignments. You can place the first person in any one of the assignments. Therefore, you have fivepeople and five assignments. Now one square is occupied, so you have four places toplace the second person, three spaces for the third person, two places for the fourthperson and only one possible place for the last person. Thus, you see that there are 120 different ways in which I could distribute five peopleamong five jobs. The order of an assignment matters, so this is known as a permutation. If I had five people and wanted to form a team of five people who were all equal, therewould be only one combination possible. I would simply assign my five people to the team. When order does not matter, there are fewer possibilities, because multiple orderings ofcommittees are counted as one combination. Here we have six separate orderings of three distinct objects, so there are sixpermutations. However, because the members of the group are constant, there is only onecombination. Let's suppose that a lottery drawing has six numbered balls in a bowl, each labeled 1through 6. We will draw four balls one at a time to identify the winning number for thelottery. There are two ways you can think about the lottery. One is to say that the order ofnumbers matters and another is to say that it does not.

If the order of a set matters, then we are dealing with permutations. Permutations describethe number of ways that a group of objects can be ordered. The positions of four objects,one through four, can be filled by drawing one object each from a set of six unique objects. So, the first ball could be any one of 1, 2, 3, 4, 5, or 6; and after drawing those 6 there are5 left. So we have any of 5 to go in the next place. And that leaves 4 more places to go,and that leaves 3 spaces left in the final place. Thus, our total number of permutations would be 6 x 5 x 4 x 3 = 360. If you are predicting the order of a lottery, then a fair bet would pay 360 to 1, or $360 on a$1 wager. The number of permutations is given by the expression n factorial / (n-m)factorial, where n and m are integers. Where the exclamation mark stands for factorial and n is the number of unique objects,such as six different orders of pancakes with different toppings. m is the number of uniqueattributes, such as four types of syrup. If n - m = 2, then there are two possiblecombinations for each attribute. In this example, we have 6 factorial / 2 factorial, which is equal to 6 x 5 x 4 x 3, or 360. On the other hand, if the lottery is a game of chance in which it doesn't matter what orderwe select the balls, we simply have to select four correct numbers. Combinations are whatwe have here. Now let us imagine that I reach into the box and pull out the number four, the number two,the number three, and the number five. Now, let's suppose that we only need to guess the correct four numbers and not theirorder. In this case, we divide 360 by 24, which means there are 15 possible combinationsof four balls. To win a lottery with a combination of 4 numbers, I would receive $15 on a $1 wager if thelottery were fair. Because now I have a 1 in 15 chance of guessing the correctcombination. The number 15 was chosen because there are 24 different ways that 4 ballscan be arranged in a row. We divide 360 by 24 to get 15. Because the first number, second number, third number, and fourth number can be first,there are three numbers that could be in second place. There would be two remaining foreach of those combinations. Since there are 4 x 3 x 2 possibilities, the general formula for this problem can beexpressed as n factorial / (n - m) factorial times m factorial.

And this formula is named n choose m. For the value of n chosen to be 6 and m equal to 4, the result is 360. Dividing this numberby 24 yields 15. Another example now. I need to send a dump truck, bulldozer, and steamroller to a construction project. I haveeight potential drivers—each of whom is qualified to operate all three machines. If I care about exactly which driver operates which machine, then I have 336 unique waysto arrange a fleet of three vehicles with eight, seven, and six drivers respectively. I have336 possible ways to send out teams of three people to drive three machines. So, here, the general formula is for permutations, which is n factorial divided by n minus mfactorial, where n equals 8 and m equals 3. So we have 8 factorial /(8-3) factorial, which is5 factorial, and that would give us 8 x 7 x 6. If the drivers are interchangeable, I want to know how many teams of three drivers I mightsend to the construction site with my vehicles. If a product has three options, I will use the formula for combinations, which is n factorialdivided by n minus m factorial times m factorial. For example, 8 choose 3 is 8! divided by5! times 3!. I will divide my previous answer by 6, and the result will be 56 possible teams that I couldsend. That’s why combinations and permutations are different concepts. Next, we need to consider the concept of with and without replacement when we define aprobability. When we draw a card from a deck, that card is removed from the deck and there is nolonger any possibility of getting that card again until we have a new hand. So, for example, if I drew an ace on my first card, I would have a 1 in 13 chance ofrepeating that feat on the second card. That probability would change if I drew a differentcard from the deck. If I were to draw an ace on my first card, the probability of doing soagain on my second card would differ from that of drawing another ace. The probability ofdrawing an ace on the second card is 3/51, since there are now three aces left in the deckout of 51 cards. Any situation in which we remove things from the realm of possibility is withoutreplacement.

But when I'm trying to predict or guess a number between 000 and 999, it's certainlyallowed to use each of the digits, 0 through 9, more than once. You can use each one twoor three times, and so there we're generating a number, with replacement. So between the concepts of permutations, combinations, and factorials, we have almost allprobability situations that are likely to arise in a basic probability course. By combining theconcepts of permutations and combinations with the concept of trials with and withoutreplacement, we can account for nearly all probability situations that can appear.