Selections, Permutations and Combinations
This article is not written for mathematicians but for the ‘intelligent layman’, or rather the ‘thoughtful’ layman — not quite the same thing since, unfortunately, it is quite possible to be highly intelligent without doing much thinking for oneself.
Many aspects of so-called elementary mathematics are much harder to grasp for the beginner than they need be, not because there are difficult or ‘deep’ questions involved but because of the specialised terminology which often conflicts with normal English usage. In some cases, there is the added problem of inconsistent or confusing notation.
Today, professional mathematicians insist on viewing their subject as a self-contained formal discipline, but there is no doubt in my eyes that our core mathematical concepts are abstractions from sense experience and there is an increasing amount of observational evidence which supports this commonsense view (see, for example, Where Mathematics Comes From, by the cognitive scientists Lakoff and Núñez, Perseus, 2000). In what follows, the bare minimum of mathematical knowledge is taken for granted, and the reader is invited to actually test what is stated by experiment and observation, using real or imagined objects.
Selections
Since the terms combination and permutation cause difficulty, I shall start by using the word Selection which, hopefully, I do not need to define.
Let us suppose we have a store, or pool, of discrete, distinguishable objects, playing cards, shirts, shrubs, whatever, and we are going to select some — or possibly all — of them. This is the sort of thing we spend our lives doing : when going into a shop we make a selection from all the goods on offer, and when preparing a meal we make a selection from the various vegetables, eggs and joints of meat available.
In practice, the number of items we choose always has an upper limit, for example, the amount of goods we can afford to buy in one day, and, similarly, there is an upper limit on the number of goods any shop can put on the shelves. This means we need not bother to consider what happens if we want to make an ‘infinite’ selection from an ‘infinite’ amount, leaving such strictly academic questions to people who have nothing better to do.
On the other hand, what may cause some surprise at first is that in mathematics not taking any of the objects on display counts as a selection — a zero selection, if you like. The main reasons for doing this are aesthetic and formal reasons, i.e. so we can have a more general theory which includes the zero case. But it is not unreasonable to view abstaining from making a selection as a sort of selection nonetheless : offered a choice of fruit for dessert I might reject everything on the menu and say I didn’t want a dessert. To ‘not-do’ something is a form of doing, or can be, nor need this involve us in any strange concepts such as the celebrated Taoist technique of achieving your aim by (apparently) not bothering whether you achieve it or not.
Both Permutations and a Combinations are Selections and the essential difference is that, in the first case, we take the ordering of the elements selected into account, whereas, in the second place, we disregard order entirely. Thus, supposing we are going to select four items which we label A, B, C and D.
ABCD is a different permutation from CDAB but it counts as the same combination because the same elements appear in the selection and only these elements. In general, as one can imagine, there are many more permutaions than there are combinations.
Permutations
Suppose we have n objects and are going to select r at a time. [Some people may feel a little uneasy with ‘number n’ but the basic idea is no different from talking about ‘a certain number of men’ or ‘a certain number of potatoes’. How many? Well, that depends on the context but it is still possible to say quite a lot about such unspecified collections of objects, for example that all the men will have one and only one head and all the potatoes will have a rounded surface.] Since we can’t select more objects than are available, r cannot be greater than n, and it is important to bear this in mind. [Unfortunately, the standard ‘smaller or equal to’ sign is not available to me at the moment.] Also, both n and r must be assumed to be positive (or just possibly zero) since we are dealing with actual, or conceivably actual, collections of objects, and with actual, or conceivably actual, choices between them.
We note any such permutation as nPr n = 0, 1, 3… (where r cannot be greater than n).
By convention n appears as an index (at the top of a letter) and r as a suffix (below the line).
Suppose we decide not to take any objects at all. There is only one way of making no choice at all, or so I assume, so nP0. = 1
We are now going to select a single object from n objects, where n is not zero. There are as many ways of doing this as there are different objects so
nP1. = n
For example, given ABCD as distinguishable elements, we can take out A or B or C or D. Here, it is easy to count the number of possibilities, but the point is to realise that there are as many single selections as there are distinguishable elements in the first place, no matter how many objects are involved. This is why we write n allowing n to take any positive value — it could be 100 or 100, 000 or a number so big it could not be written down on this sheet of paper.
Suppose we take two objects from n (where n is at least 2) and arrange them in a series of boxes or pigeonholes which (I find I cannot symbolize with this treatment).
For the first position we have n choices — the case we have already considered. This means, whatever we chose, there is one less possibility for the second box, i.e. (n-1) possibilities. Thus, if we had chosen A out of ABCD we would be reduced to choosing from BCD for the next box, with the possibilities AB, AC, AD in all. [Note that, we are not allowed to repeat our first choice since we assume that the n objects are different and are not replaced until we have concluded the selection. The case where we allow repetition is more complicated and is best left alone for the moment.]
We have thus three selections with A in the first box. But there is nothing special about A and exactly the same sort of thing will apply to any of the other suit cards. And since there are four suits, we end up with 3 ´ 4 permutations in all. Thus
4P2. = 4 ´ 3 = 12 or more succinctly using a dot to indicate multiplication 4P2. = 4 .3 = 12
There is nothing special about the number 4 and a little thought will convince you that, no matter what the value of n, there will be n ´ (n-1) permutations or
nP2. = n ´ (n-1) or n (n-1) for short.
If you are unconvinced by this, convince yourself by putting a certain number of actual objects on the table and seeing how many different pairs you can make. But remember that, since we are speaking of permutations, two objects in a different order will make two permutations. Thus an envelope placed to the right of a pair of scissors *“ is one permutation and “* is a different one.
We now choose three objects out of n. Once again we will consider the case of just four objects symbolized as A B C D. The possibilities can be represented in a tree diagram where you follow down a pathway from §
A
B C D
C D B D B C
The total possibilities are ABC, ABD, ACB, ACD, ADB, ADC i.e. six in all.
Again, the same will apply to the other choices for first place, B, C and D and since there are four suits we end up with 6 ´ 4 = 24 permutations of 4 objects, taking 3 at a time.
Thus 4P3. = 2 ´ 3 ´ 4 = 4 ´ 3 ´ 2 = 24
Generalizing to n objects, we can perhaps agree that
nP3. = n ´ (n-1) ´ (n-2) = n(n-1)(n-2)
Note that the last digit we subtract is 2, appearing in (n-2) and that this is one less than the number of boxes which is the suffix digit, 3.
Proceeding in this way, you will perhaps soon be able to produce a completely general formula for a permutation of r objects taken from a store of n original objects. I repeat once more the important proviso that we are not allowed repeats : once we have, for example, used § in a single selection, we cannot use it again in the same selection (though we can, of course, use it again in a further selection because we return it to the store).
The formula is
nPr = n(n-1)(n-2)(n-3)……..(n-r+1)
The part where one is most likely to make a mistake is where you cut off the multiplication process. One might suppose that you end up with (n-r) since there are r boxes with one object in each. But, if you look carefully, you will see that we start with n or, if you like, (n-0), and so, if we want there to be r objects in the r boxes, we must end up not with r but (r-1) . This number is going to be subtracted, so we get (n – (r-1)) or, following the rule about “a minus from a minus makes a plus”, we can write (n-r+1). You might fear that this is going to go negative which would give a ridiculous result since the entire product would turn out to be negative. But this cannot happen as we have stipulated in the beginning that r can never overtake n, or r £ n The largest number of permutations of n objects is obviously going to be when we use the whole lot of them, i.e. r = n . Fitting in this value of r we get n(n-1)(n-2)(n-3)……..(n-n+1) and since (n-n) = 0 this turns out to be n(n-1)(n-2)(n-3)……..(1) i.e. a multiplication involving all the numbers from 1 to n inclusive. This case is so important in mathematics that it has a special notation n! where the ! does not indicate surprise, as in normal speech, but is best conceived as an instruction to multiply n by all the numbers less than it down to 1. Incidentally, if you find the exclamation mark notation annoying at first, you are in good company since, when it was first proposed in the mid-nineteenth century the Royal Society thought the same.
The so-called factorial numbers n! with n = 1, 2, 3… get very large surprisingly quickly. Take a guess at how large 8! is. One might imagine it was below the thousand mark but it actually turns out to be 40,320 .
On most pocket calculators, you can simply key in two digits and obtain the number of possible permutations of n objects taking r at a time, but this will teach you nothing about what all this means, nor will this familiarise you with handling numbers. It is more instructive to make an original guess at nPr for different values of n and r, then perform the multiplications with pen and paper using short cuts (even better in your head) and finally check your result. Thus, I might guess if there are 10 objects and I take 4 at a time, the total permutations will be around 1,500. Multiplying out
11 ´ 10 ´ 9 ´ 8 = 110 ´ 72 = 110 ´ 72 = 7200 + 720 = 7920 which turns out to be correct. Once again the number of permutations is improbably large — though still perfectly testable provided one has plenty of time and patience.
Combinations
nCr
The term is most misleading since a combination in the sense of ‘a combination lock’ is an arrangement of numbers in a specific order, say, 15678. This ‘combination’ is not the same as 78651 since, using the latter, you would not be able to open the lock. Now, this is not the mathematical sense according to which the two different permutations 15678 and 78651 constitute the same combination — since the selfsame digits appear and no others. In practice, we are more often concerned with combinations than permutations. For example, if I select half a dozen books to take with me on holiday, it is quite unimportant how they are packed in my case, or how they were arranged on the shelf — all that matters is that I have them and that I don’t have duplicate copies of the same book.
In the so-called trivial case of selecting nothing at all, i.e. r = 0, there is no difference between a permutation and a combination. Also, if we restrict ourselves to selecting a single object from the pool, i.e. r = 1, there’s nothing to permute either — we either select this object or we don’t. Thus, noting combinations as nCr we can say straightaway
nC0 = nP0 = 1 and nC1 = nP1 = n
For any other selection, the number of permutations of r objects looks as if it is going to be larger than the number of combinations. How much larger?
If we have just four objects in a pool, say A B C D, the number of permutations, taking them all at a time, will be 4! = 24 — a case we have already considered and which is not too large an amount for you to check using actual objects.
However, all these twenty-four permutations constitute a single combination, since the four objects, and no others, appear each time, albeit in a different order. So the ratio permutation : combination is 24 : 1. A little thought will hopefully convince you that this will be the same whatever the number of objects we select. Any permutation of r objects will constitute a single combination, whatever r is. So, to obtain the number of combinations we simply have to divide by the factorial r! In the example given above we were considering the permutations of A B C D where we select all of them, but we can also consider the case where we select only two objects out of the four. The number of permutations would then be
4P2 = 4.3 = 12
According to the principle just enunciated, the number of combinations should be 12 divided by 2! or 12/2 = 6 . By trial, this turns out to be correct since the only possibilities are AB, AC, AD, BC, BD and CD.
Note that there are exactly two terms in the multiplication, 4P2 = 4.3 corresponding to two boxes ÿÿ in which we are going to put two objects, one in each. Also, it is worth pointing out that, although there are n terms in factorial n! there are only (n-1) that we need bother about since the first (or last) number is 1 and anything multiplied by 1, i.e. taken once, is just that quantity.
If the reader accepts the preceding, at any rate provisorily, we can state a general formula for the number of combinations of n objects taking r at any one time where r £ n. Since the ratio permutation : combination is r! : 1 we simply divide by factorial r :
Thus,
nCr = nPr /r! = (n(n-1)(n-2)(n-3)……..(n-r+1))/ r!
This may look complicated but in practice comes out quite easily. For example, supposing I want to calculate the ways of selecting 5 objects from a pool of 10 different objects, I first calculate 10P5 = 10 ´ 9 ´ 8 ´ 7 ´ 6 = 30240
5 digits
and now divide by 5! = 5 ´ 4 ´ 3 ´ 2 ´ 1 = 5 ´ 24 = 120 . 30240/120 = 252.
5 digits
Thus 10C5 = 252
As it happens, the formula actually works in the case when we pick a single item from n objects. If you substitute 1 for r in the formula above you get just the single entry (n–1+1) = n on top and 1! On the bottom. Since multiplying 1 by all the numbers back to 1 is just 1, the bottom line is just 1. And so we have
nC1 = 1/1 = 1
In the case of taking nothing at all, r = 0, the formula does not really work since (n–0+1) = (n+1) which means we have more objects than we actually have which is absurd, and the bottom line is factorial 0 or 0! which seems meaningless. We can, however, simply define nC0 as being 1 for all n, and similarly define 0!, if it should crop up elsewhere as being equal to 1. This does no harm and allows us to have a completely general formula with predictions which correspond to what actually happens in the real world.
Most modern textbooks give the Combination Formula in a slightly different form, namely
nCr = n! .
r! (n–r)!
which is neater but much less helpful to the beginner since it does not show the link with permutations, and does not allow you to count the r terms in the multiplication process. Then end result is the same because there are in effect a whole lot of terms in the numerator and denominator which cancel out. To see this, note that in the formula as I give it, there are r terms in the numerator ending with (n-r+1). If we are to carry on multiplying back to 1 the very next term will be (n–r) , the one after that (n–r–1) and so on ending with 1. This means we have multiplied right back from n to 1 so this is so-called factorial n written n! To equalize, we need to multiply the bottom by the same amount, in this case the sequence between (n-r+1) and 1, or factorial (n–r) = (n–r)!
As an example, take 10C5 which we just quoted. Here, n = 10 and r = 5 and so, fitting in these values to the new formula, we have
= 10! . = 10.9.8.7.6.5.4.3.2.1.
5! (10–5)! (5.4.3.2.1.) ´ (5.4.3.2.1.)
= 3628800 = 252 as before.
120 ´ 120
[It is purely accidental that, in this case, we get 120 twice in the denominator — this is simply because, in this case, (n–r) = r since (10 – 5) = 5.]
We can, on this basis, start to set up a table of combinations.
Leaving aside the case of making a zero selection from a zero collection — a special case which messes up the general pattern, we start with selecting 1 object from a store containing 1 object only. We know about this already : there is only one way of doing this.
We then pass to the number of combinations of how to select 1 object from a store of 2, then the number of ways of selecting 2 objects from a store of 2 and so on. If you follow the rule set out above, i.e. dividing the number of permutations by the value of r (the number of objects selected), you should start building up a table like this one :
0 1 2 3 4 5 ………………….
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
………………………………………………..
The row number, marked in red on the left, most confusingly (for English speakers) indicates the objects in the store, starting at 0, while the columns indicate the number of objects selected. Thus, the n in nCr becomes the row number, while the r becomes the column number. One gets used to this, but it is quite infuriating at first and neither mathematics books nor teachers sufficiently emphasize this point.
To find out, say, how many ways you can select 3 objects from a store of 5 distinguishable objects, you look along row 5 and down column 3. This gives 10 . So there are ten ways of doing this which we can check by working it out from first principles. 5P3 = 5.4.3 = 60 and if we divide by r! = 3.2.1. = 6 we obtain 10 as expected. Also, using the other formula
5C3 = (5.4.3.2.1.) = 120/12 = 10
(3.2.1) ´ (2.1.)
Them manner in which one builds up the entries should be apparent if you look closely so there is no need to work out the individual entries once you have a few to start with.
The above, as you probably know, is Pascal’s Traingle, an array first defined and investigated in the West by the scientist and religious mystic, Blaise Pascal, who pointed out many curious and interesting features of these numbers and the way they come together. Actually, the selfsame array was known to the melancholy hedonist Omar Khayyàm centuries earlier — he was, surprisingly, an astronomer and mathematician apart from being a lyric poet and wine-taster — and earlier still in China. So this collection of numbers has been going for nearly a thousand years already, attracting the attention of mathematicians across the globe, and certain hitherto unknown features are still being investigated today. This probably makes it, along with the Fibonacci Sequence and the Prime Numbers Sequence, the most prestigious collection of numbers in mathematics.
Sebastian Hayes
Sebastian Hayes 
Karla said,
April 16, 2014 at 9:57 am
I really like it when individuals get together and share views.
Great site, continue the good work!