This section covers permutations and combinations. Show Arranging Objects The number of ways of arranging n unlike objects in a line is n! (pronounced ‘n factorial’). n! = n × (n – 1) × (n – 2) ×…× 3 × 2 × 1 Example How many different ways can the letters P, Q, R, S be arranged? The answer is 4! = 24. This is because there are four spaces to be filled: _, _, _, _ The first space can be filled by any one of the four letters. The second space can be filled by any of the remaining 3 letters. The third space can be filled by any of the 2 remaining letters and the final space must be filled by the one remaining letter. The total number of possible arrangements is therefore 4 × 3 × 2 × 1 = 4!
n!
. Example In how many ways can the letters in the word: STATISTICS be arranged? There are 3 S’s, 2 I’s and 3 T’s in this word, therefore, the number of ways of arranging the letters are: 10!=50 400 Rings and Roundabouts
When clockwise and anti-clockwise arrangements are the same, the number of ways is ½ (n – 1)! Example Ten people go to a party. How many different ways can they be seated? Anti-clockwise and clockwise arrangements are the same. Therefore, the total number of ways is ½ (10-1)! = 181 440 Combinations The number of ways of selecting r objects from n unlike objects is: Example There are 10 balls in a bag numbered from 1 to 10. Three balls are selected at random. How many different ways are there of selecting the three balls? 10C3 =10!=10 × 9 × 8= 120 Permutations A permutation is an ordered arrangement.
nPr = n! . Example In the Match of the Day’s goal of the month competition, you had to pick the top 3 goals out of 10. Since the order is important, it is the permutation formula which we use. 10P3 =10! = 720 There are therefore 720 different ways of picking the top three goals. Probability The above facts can be used to help solve problems in probability. Example In the National Lottery, 6 numbers are chosen from 49. You win if the 6 balls you pick match the six balls selected by the machine. What is the probability of winning the National Lottery? The number of ways of choosing 6 numbers from 49 is 49C6 = 13 983 816 . Therefore the probability of winning the lottery is 1/13983816 = 0.000 000 071 5 (3sf), which is about a 1 in 14 million chance. I’ve always confused “permutation” and “combination” — which one’s which? Here’s an easy way to remember: permutation sounds complicated, doesn’t it? And it is. With permutations, every little detail matters. Alice, Bob and Charlie is different from Charlie, Bob and Alice (insert your friends’ names here). Combinations, on the other hand, are pretty easy going. The details don’t matter. Alice, Bob and Charlie is the same as Charlie, Bob and Alice. Permutations are for lists (order matters) and combinations are for groups (order doesn’t matter). You know, a "combination lock" should really be called a "permutation lock". The order you put the numbers in matters. A true "combination lock" would accept both 10-17-23 and 23-17-10 as correct. Permutations: The hairy detailsLet’s start with permutations, or all possible ways of doing something. We’re using the fancy-pants term “permutation”, so we’re going to care about every last detail, including the order of each item. Let’s say we have 8 people:
How many ways can we award a 1st, 2nd and 3rd place prize among eight contestants? (Gold / Silver / Bronze) We’re going to use permutations since the order we hand out these medals matters. Here’s how it breaks down:
We picked certain people to win, but the details don’t matter: we had 8 choices at first, then 7, then 6. The total number of options was $8 * 7 * 6 = 336$. Let’s look at the details. We had to order 3 people out of 8. To do this, we started with all options (8) then took them away one at a time (7, then 6) until we ran out of medals. We know the factorial is: Unfortunately, that does too much! We only want $8 * 7 * 6$. How can we “stop” the factorial at 5? This is where permutations get cool: notice how we want to get rid of $5 * 4 * 3 * 2 * 1$. What’s another name for this? 5 factorial! So, if we do 8!/5! we get: And why did we use the number 5? Because it was left over after we picked 3 medals from 8. So, a better way to write this would be: where 8!/(8-3)! is just a fancy way of saying “Use the first 3 numbers of 8!”. If we have n items total and want to pick k in a certain order, we get: And this is the fancy permutation formula: You have n items and want to find the number of ways k items can be ordered: Combinations are easy going. Order doesn’t matter. You can mix it up and it looks the same. Let’s say I’m a cheapskate and can’t afford separate Gold, Silver and Bronze medals. In fact, I can only afford empty tin cans. How many ways can I give 3 tin cans to 8 people? Well, in this case, the order we pick people doesn’t matter. If I give a can to Alice, Bob and then Charlie, it’s the same as giving to Charlie, Alice and then Bob. Either way, they’re equally disappointed. This raises an interesting point — we’ve got some redundancies here. Alice Bob Charlie = Charlie Bob Alice. For a moment, let’s just figure out how many ways we can rearrange 3 people. Well, we have 3 choices for the first person, 2 for the second, and only 1 for the last. So we have $3 * 2 * 1$ ways to re-arrange 3 people. Wait a minute… this is looking a bit like a permutation! You tricked me! Indeed I did. If you have N people and you want to know how many arrangements there are for all of them, it’s just N factorial or N! So, if we have 3 tin cans to give away, there are 3! or 6 variations for every choice we pick. If we want to figure out how many combinations we have, we just create all the permutations and divide by all the redundancies. In our case, we get 336 permutations (from above), and we divide by the 6 redundancies for each permutation and get 336/6 = 56. The general formula is which means “Find all the ways to pick k people from n, and divide by the k! variants”. Writing this out, we get our combination formula, or the number of ways to combine k items from a set of n: Sometimes C(n,k) is written as: which is the the binomial coefficient. A few examplesHere’s a few examples of combinations (order doesn’t matter) from permutations (order matters).
Don’t memorize the formulas, understand why they work. Combinations sound simpler than permutations, and they are. You have fewer combinations than permutations. Other Posts In This Series
Why is it important to study combination?The big idea of combination learning is shifting the focus from content to the process of learning. Combination Learning allows teachers and students to work together to 'mash' bits and pieces of learning to design entirely unique and personalized learning scenarios.
What is combination important?The combination is a way of selecting items from a collection, such that (unlike permutations) the order of selection does not matter. In smaller cases, it is possible to count the number of combinations. Combination refers to the combination of n things taken k at a time without repetition.
What is meant by combination in mathematics?In mathematics, a combination is a way of selecting items from a collection where the order of selection does not matter. Suppose we have a set of three numbers P, Q and R. Then in how many ways we can select two numbers from each set, is defined by combination.
Does combination matter?When the order doesn't matter, it is a Combination. When the order does matter it is a Permutation.
|