Business Home Page |
Permutations and Combinations Introduction Of course we all would like to win the lottery or the football pools or the sweepstake … and of course we don't. The big question is, why don't we win these things so easily? What's to stop me from choosing my six numbers and winning the UK lottery one Saturday evening and retiring to the desert island that I will be able to buy with the winnings? Well, there's nothing to stop us winning anything: after all, all we have to do is to choose the correct six numbers! The most important point to remember is that in order to win the lottery we have to find EXACTLY the right combination of six numbers that will win us the millions we dream of. Take it from us for now but if we have to select 6 numbers from 45 on a lottery ticket, there are, in fact, 5,864,443,200 ways of doing that. If we have to choose 6 numbers and there are 49 numbers to choose from on the lottery ticket, there are 10,068,347,520 ways to do that. If we want to win the football pools, where we need to predict 8 score draws from 55 games played, we can choose 8 numbers from 55 numbers in 49,092,275,232,000 different ways We can start to see now why it's difficult to win the lottery, the football pools and the sweepstake! In the same way, imagine that we have a group of people who can be assigned to jobs or to rooms or to cities in certain combinations only, such as in sub groups of two or three or four, we find that there are only so many ways in which such sub groupings can be achieved. For example, imagine that we have 45 people and we want to split them into groups of six people: how many ways are there to do that? There are 8,145,060 groupings of six people when we have a total of 45 people to choose from. Huge numbers aren't they? Notice, though, that the number of ways to combine people is a lot less than the ways in which we can choose our lottery numbers … let's see why now. Permutations and Combinations So far we have talked generally about permutations and combinations and we have seen some huge numbers developing out of much smaller numbers. Let's shrink the numbers now, then, and talk about permutations first and then combinations to see exactly what it is that we are talking about and trying to achieve. Permutations A permutation is defined as being an ordered arrangement or grouping of a set of numbers, items etc and any one of a range of possible groupings, according to the Concise Oxford Dictionary. Oakshott adds that in the case of permutations, the order of selection is important. Let's take a simple example of what a permutation really means: Imagine that we are choosing two subjects to study out of a total of three different subject: Maths, English and Science. We want to know how many ways in which we can select our two subjects from the three on offer: Permutations We find a total of six permutations of our three subjects if we want to chose them in groups of two. Example Two Imagine now that we have been given greater choice: now we have four subjects to choose from. We want to know the number of ways in which we can choose two subjects from four: Maths, English, Science and Art. Here we are: Permutations … a total of 12 permutations or ways in which we can put together two subjects from the four available. For you to do: Imagine now that French is added to the list of subjects available for you to choose from. How many ways are there now in which you can choose two subjects from the five on offer? Did you get 20 different ways? Good! Unrealistic Method! What we have seen so far is fine but the method we have used isn't exactly realistic is it? For example, if you are about to choose your options at school or university and you have 15 subjects to choose any three from and you are interested to find out how many ways in which you might choose your three subjects, you wouldn't want to make a list of them like we've been doing so far: after all, there are 2,730 permutations of 3 from 15 … 32,760 when we are perming 4 from 15 … and so on. One way of dealing with this problem, though is to imagine that you have, say, three numbers, 1, 2 and 3 to arrange. How many ways are there to arrange them? This is how many:
That is, for our first number choice, we can choose from all three available numbers; for the second number we only have two numbers to choose from and for the final number ... well, there's only one left. Hence the number of ways of arranging 1, 2 and 3 is 3 * 2 * 1 = 6 ... try it, it really works! Try this now: you have the letters A, B, C and D to arrange in a group. You want to know how many different ways you can arrange them. Here's the solution to that problem.
That is, for the first letter, you can choose from all four letters, for the second placed letter, you can only choose from the three that are left; and so on. The number of ways for organising these four letters, then, is 4 * 3 * 2 * 1 = 24. Try it, see if you can find all 24 ways! Thanks to my correspondent Dave for encouraging me to add the above new explanation and examples. Mathematicians to the Rescue! As ever, the world's mathematicians have done all the necessary work for us and they have developed a relatively simple formula for us to work with as we seek answers to these permutation problems. Permutation Formula: n!/(n-r)!) (A huge thanks to a friend of this site who wrote and pointed out that I had previously put the wrong formula here ... unfortuantely I deleted his message before I came and made this correction. I am eternally grateful for the correction) where
n is the group size n! = 5 x 4 x 3 x 2 x 1 (n - r)! means the factorial of the result of having subtracted r from n. Reworking our examples we can use this formula now, starting with the smallest and easiest numbers: Subjects:
perm 2 from 3, 2 from 4, 2 from 5 then 3 from 15 2 from 3 subjects: 3!/(2!*(3-2)!) = 3 2 from 4 subjects: 4!/(2!*(4-2)!) = 6 2 from 5 subjects: 5!/(2!*(5-2)!) = 10 3 from 15 subjects: 15!/(3!*(15-3)!) = 455 6 from 45 lottery numbers: 45!/(6!*(45-6)!) = 8,145,060 We used Excel to evaluate this for us, you can do the same or use your calculator; but if you want to see what 45! looks like, here it is (see the note at the end of the page): 45! = 119,622,220,865,480,000,000,000,000,000,000,000,000,000,000,000,000,000,000 6 from 49 lottery numbers: 49!/(6!*(49-6)!) = 13,983,816 8 from 55 draws on the football pools: 55!/(8!*(55-8)!) = 1,217,566,350 Further Examples 1 If you want to think about permutations a little more, you can evaluate the number of possible PIN numbers that a bank can assign to a credit or debit card. Calculate the possible number of PIN numbers that can be generated when the bank uses 4 digits for a PIN. Assume for this calculation, as for any permutation calculation, that once you have used a number it cannot be used again. Did you get 210? 2 The combination lock on the safe at the local Sportsmen's Club has 100 numbers around it and the combination itself is four digits long. I Crackem is a burglar and he knows all about the safe … how many different permutations would he have to take into account if he were to guarantee to be able to open the safe? Did you get 161,700? As a matter of interest, Mr Crackem, you need to know the length of the code before you can even begin to crack it. In other words, if the Club's safe had a 3 from 100 code, you know that there are 970,200 different arrangements of the numbers … consider a code that is 4 from 100 (94,109,400) or 5 from 100 (9,034,502,400) … don't give up your day job and forget sitting in the vaults with your stethoscope glued to the door of the safe waiting for all those clicks, it just isn't going to happen! A huge thanks to Eddie Opperdoes for correcting the above section: I inadvertently used the wrong formula and have now made the corrections. It might be clear now that permutations take ALL digits, subjects, variables into account and they discard none of them as they assess the total number of permutations available or required. Nothing wrong with that since that's exactly what is supposed to happen and, taking the two from three subjects example to demonstrate what this means, we have, as we saw before: Permutations Notice here that there is some repetition in this list in that permutation 1 is really the same as permutation 3; 2 is the same as 5; and 4 is the same as 6. That is, this example shows us that when we derive the permutations from lists of digits, subjects variables and so on, we generate repetitions. However, remember the definition of permutations that said A permutation is defined as being an ordered arrangement or grouping of a set of numbers, items etc and any one of a range of possible groupings, according to the Concise Oxford Dictionary. Oakshott adds that in the case of permutations, the order of selection is important. A numerical example will show why the ordering of numbers in a permutation is important. Let's imagine that the Sportsmen's Club's safe has only 3 numbers around it: 1, 2 and 3; and they have a 2 digit code, this gives us the following possibilities: Permutations With the two from three subjects example, we would say that permutations 1 and 3 were equivalent to each other since they both have the numbers 1 and 2 in them. Similarly, we would say that permutations 2 and 5 are equivalent since they have the numbers 1 and 3 in them. However, here we can see that if we tried 1 2 instead of 2 1 and 2 1 is the correct code, the safe would not open … this is an example of why we say that ordering is important with permutations. The ordering aspect, therefore, is a vital point that we need to explore a little more; and that takes us on to combinations. Combinations A combination is defined by the Concise Oxford Dictionary as a group of things chosen from a larger number without regard to their arrangement. In other words, we are not concerned with examples such as the codes that open safes, the winning numbers in a lottery and such problems. We are, however, concerned with such problems as choosing subjects from a given list, from working out the possible results from betting on the tossing of a coin and so on. Let's go back to the choice of two from three subjects example we have already seen, as follows:
and for the two from four subjects we have:
For You to Do: work down the table for the two from five subject now … how many subjects can be chosen by permutations and by combinations? Did you get 20 and 10 respectively? Have you spotted that the combinations results return only UNIQUE sets of values? That is, with combinations, we can only choose maths and English but not English and maths; English and science but not science and English. Mathematicians have devised a formula to deal with these situations:
where
n is group size Let's apply this to the two subject from three, two from four subjects and then three from 15 subjects:
If we add the two subjects from five subjects (maths (M), English (E), science (S), art (A) and French (F)) table, we will see that there is a pattern to the way that combinations stem from permutations:
If we were to translate these subjects into numbers, we would have: Maths (1), English (2), Science (3), Art (4) and French (5) Putting all three tables together with numerical values only gives us:
See the pattern? In fact, we can predict that if we were asked to consider choosing two from six subjects, we would have 15 combinations to choose from … can you see how we got that? Look carefully then agree that there would be 21 combinations of subjects to choose from if we were given two subjects to choose from seven possible. It might help you to see this pattern. If we were asked to choose three subjects from three then four then five … the total combinations would be: 1, 4, 10, 20, 35 … complete the series! Try this: how many ways are there of getting four heads from 10 tosses of a coin? In fact, there are 210 ways for getting four heads from 10 tosses of a coin. We won't bother with listing all 210 ways so we'll use the mathematician's formula: In this case the formula gives us
Excel Functions Microsoft Excel has been programmed with permutations and combinations in mind: =PERMUT(n,r) gives the permutations from a group size of n with r chosen at a time =COMBIN(n,r) gives the combinations from a group size of n with r chosen at a time Simplicity itself! Praise Excel! In case it helps a little, here are two tables: firstly the first batch of permutations starting with n = 1 and r = 1 and working up to n = 7 and r = 7
Similarly for combinations, also ranging n = 1 and r = 1 and working up to n = 10 and r = 10
Acknowledgement 1 A huge thanks to Eddie Opperdoes for correcting the above section: I inadvertently used the wrong formula and have now made the corrections; and to the friend who corrected my permutations formula. 2 Russel John kindly wrote to me this week to advise me as follows: Actually, since Excel only works to 16 significant figures, this is an approximate value for 45! It is difficult to get an exact figure, unless your computer works to 64 significant figures. E.g. My computer's inbuilt scientific calculator returns 119,622,220,865,480,194,561,963,161,495,660,000,000,000,000,000,000,000,000 which is only accurate to 32 significant figures. You might have more luck with a computer using the new 64 bit technology. Things go haywire for Excel around 20!. Multiply 20! by 21 on a piece of paper and compare it with Excel's answer for 21!. This highlights the dangers of using factorials directly in combinatoric formulae. You very quickly hit machine constraints and can be plagued by round off error if you aren't careful. It also underlines the fact that you need to be extremely cautious in Excel if extremely large (or small) numbers are involved in calculations. I accepted what Russel told me and after a brief exchange, Russel added this for us: As far as the question ... about how high can Excel go, the answer in Excel 2003 and 2007 is 170! After that you get a #NUM error, which means the number exceeds some machine or programme constraint. That is, it is too big to be stored in the space allocated to a single number. These are seriously large numbers, increasing much faster than exponentially (as Stirling's formula shows). References Les
Oakshott (1994) Essential elements of business statistics DPP ©
Duncan Williamson |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
© Webmaster Duncan Williamson 2003 - 2009 |