Concepts: counting principle, factorial and permutations
Permutations and Combinations24 min readLesson 2 of 6
2.1 Counting without listing
Every counting problem in this chapter can be solved by imagining the choices one after another. If the first choice has m options and, after it is fixed, the second has n options, the number of complete outcomes is m times n. This is the fundamental principle of counting, and it extends to any number of stages. A tree diagram draws the stages as branches and each full path from the start to a tip is one outcome.
A simple example makes the multiplication visible. A school bag can be chosen in 2 ways, a tiffin box in 3 ways and a water bottle in 2 ways. Going bag, then box, then bottle gives 2 times 3 times 2 equal to 12 combinations. The tree has two main branches, each splitting three ways, and each of those splitting two ways, so twelve tips appear.
The addition principle covers alternatives rather than stages. If a task can be done through one family of options with m outcomes or through a disjoint family with n outcomes, the total is m plus n. The two principles combine in one question when the first letter of a code is chosen in one set of ways and the remaining letters in another.
2.2 Digits, codes and factorials
A typical first exercise asks for three digit numbers from the digits 1 to 5. With repetition allowed, each of the three places has 5 options, so the count is 5 to the third power, that is 125. Without repetition, the first place has 5 options, the second has 4 because one digit is used, and the third has 3, giving 5 times 4 times 3 equal to 60.
Codes and telephone numbers follow the same pattern, with one extra rule to watch: a leading zero is not allowed in a number, so count choices for the first place separately. A five digit number starting with 67 has three remaining places, each filled from the digits 0 to 9 without repetition, which gives 8 times 7 times 6 equal to 336.
The product in these examples is where factorial notation enters. The number of arrangements of all n different objects is n times (n minus 1) and so on down to 1, written n factorial. For arranging only r of the n objects, the product stops after r factors and is written nPr. The factorial form is nPr equal to n factorial divided by (n minus r) factorial, because the unused factors cancel. Remember that 0 factorial is 1, which keeps the formula valid when r equals n.
Slideshow, slide 1 of 3. Use the left and right arrow keys to change slides and the space bar to play or pause.
Tree diagram for forming a two digit arrangement from three letters, showing six possible outcomes
2.3 The permutation formula and its meaning
The formula nPr equals n factorial divided by (n minus r) factorial counts the ways to fill r ordered places from n distinct objects. Read it as a product of r descending factors: for 8P3 the product is 8 times 7 times 6 equal to 336. When the numbers are large, cancel factorials instead of expanding them; so 12 factorial by 9 factorial is 12 times 11 times 10.
Two special cases are worth naming. When r equals n the count is n factorial, because every object is used and all permutations of the whole set are allowed. When r equals 1 the count is n, which matches the number of choices for a single place.
A third case is repetition. If each of the r places may reuse any of the n objects, the count is n to the power r. So a three digit number from digits 1 to 5 with repetition has 125 possibilities, while the same question without repetition has 60. The gap between the two numbers is a good check that the right case was used.
2.4 Exercise 6.1 and 6.2 shapes
Exercise 6.1 is built on the multiplication principle with repetition allowed or not. Question 1 wants three digit numbers from 1 to 5 in two cases, giving 125 and 60. Question 4 is the telephone number starting with 67, which gives 336. Question 5 is a coin tossed three times, which gives 2 cubed equal to 8 outcomes. Question 6 uses five flags taken two at a time, which gives 5P2 equal to 20 signals.
Exercise 6.2 is factorial practice: evaluate 8 factorial, test whether 3 factorial plus 4 factorial equals 7 factorial, simplify ratios, and solve small equations such as 1 by 8 factorial plus 1 by 9 factorial equal to x by 10 factorial. In that last question, rewrite the tenth factorial as 10 times 9 times the eighth factorial and multiply through, which gives x equal to 100.
Both sets reward a clean first step. For a number or code question, mark the places and write the number of choices above each place before multiplying. For a factorial equation, write the largest factorial as a product that contains the smaller ones.
Common mistake
Factorials do not add: 3 factorial plus 4 factorial is 30, not 7 factorial. Only products and quotients of factorials can be simplified by cancelling common factors.