If you ever happen to get your hands on a scientific calculator, you’ll notice a smorgasbord of intriguing symbols and letters – ‘nPr’ and ‘nCr’ to name a couple. These functions calculate permutations and combinations respectively – useful if you wanted to calculate the probability of you winning the lottery (there are far more significant applications, of course.)
Suppose you had a lot of time on your hands and you wanted to compile a dictionary which contains every possible six-letter English word that can ever exist. How many words would be in the dictionary?
There are 26 letters to choose from for the first letter, 26 letters to choose from for the second letter, and so on. The number of possible words would be 26 × 26 × 26 × 26 × 26 × 26, or in shorthand form, 266. This comes out to 308,915,776 (which is nearly the population of the USA). You’d be compiling for a long time!
309 million is a tad too many for your liking, so instead you exercise a rule – you can only use the letters A to F. This dramatically reduces the size of the dictionary down to only 66 = 46,656 words, which is sufficiently few to fit in a modest pocket-sized dictionary. The Second Edition of the Oxford English Dictionary lists 273,000 words, in comparison.
You still want to shorten the dictionary, so you exercise another rule – there cannot be two of the same letter in the same word. This decreases the size of the dictionary again, but by how much? There are 6 letters to choose from for the first letter, but only 5 for the second letter, because you can’t choose the letter that you’ve already used for the first letter. For the third letter, there are only 4 options because you can’t choose the letters that you’ve used for the first two letters. The new number of possible words is then 6 × 5 × 4 × 3 × 2 × 1 = 720. This can be written in shorthand using the factorial notation (!) where the factorial of 6 is 6! = 6 × 5 × 4 × 3 × 2 × 1. For instance, the factorial of 10 would be 10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1.
So when do we get onto permutations? In fact, the example above is an example of a permutation. The number of permutations is the number of ways we can order a group of items. The group of items we ordered was the letters A to F, and we found that the number of permutations was 720.
It becomes slightly more complicated if we’re given more options to choose from. Say we had all 26 letters now instead of just A to F, then how many six-letter words could we make? Keep in mind the rule that we can’t use the same letter twice, as that condition maintains this as a permutation. There are 26 letters to choose from for the first letter, 25 letters to choose from for the second letter, and so on. The number of possible words would be 26 × 25 × 24 × 23 × 22 × 21 = 165,765,600. You might notice this is almost like a factorial but not quite. In fact, this can be concisely represented by the expression: 26! ÷ 20!, or 26! ÷ (26-6)!.
This is exactly what the nPr function calculates. If you are given a choice of n items (for example 26 letters) and you are allowed to select r items out of those (for example 6 letters out of those 26), then nPr is the number of permutations. And this is concisely given by the formula:
as we have shown.
There are of course better uses for permutations than for calculating the size of an imaginary dictionary… and also keep an eye for a post on combinations, which are different from permutations in one small but significant way.