Counting Techniques
Senior 6 · Basic Mathematics
Counting Techniques
Lesson 3 of 5
25 min
Six different textbooks stand on a shelf: Mathematics, Kiswahili, English, Geography, History and Entrepreneurship. In how many orders can they stand? By the product rule there are 6 choices for the first place, 5 for the second, and so on: . Products like this appear so often that they have a name and a symbol.
Definition
For a positive integer , factorial is . By definition .
A permutation is an arrangement of objects in a definite order. The number of permutations of different (unlike) objects in a row is .
Example: ; four runners can finish a race in 24 orders (no ties).
For every , . Putting gives , and since , we need . It also makes sense: there is exactly one way to arrange nothing.
When two objects must stand together, tie them into one block. Arrange the block with the other objects, then multiply by the number of ways to order the objects inside the block. When they must be apart, subtract the "together" arrangements from the total.
Worked example
Worked example 1. The six books are arranged on the shelf. In how many arrangements (a) are Mathematics and Kiswahili next to each other; (b) are they not next to each other; (c) is Mathematics at the left end?
(a) Block [Mathematics, Kiswahili] + 4 other books = 5 items: orders. Inside the block, 2 orders. Total .
(b) .
(c) Mathematics is fixed; the other 5 books fill 5 places: .
Arrange the letters A, A, B. If we label the A's as and , there are arrangements. But once the labels are removed, the arrangements come in pairs that look identical: each pattern was counted times, once for each order of the two A's.
In general, every pattern is counted once for each way of permuting the identical objects among themselves, so we divide by those factorials.
Definition
Permutations with identical objects. The number of arrangements in a row of objects, of which are alike of one kind, alike of another, of another, and the rest all different, is
Example: the letters of RWANDA (6 letters, A twice) give arrangements.
Worked example
Worked example 2. How many arrangements are there of the letters of (a) AKAGERA; (b) NYABARONGO?
(a) 7 letters with A three times: .
(b) 10 letters: N twice, A twice, O twice, and Y, B, R, G once each:
Worked example
Worked example 3. For the letters of AKAGERA, how many arrangements (a) begin with K; (b) have all three A's together?
(a) Fix K first. The other 6 letters, A, A, A, G, E, R, are arranged: .
(b) Glue AAA into one block. Arrange the block with K, G, E, R: 5 different items, . The block's inside has only one order (the A's are identical), so the answer is 120.
Eddie Woo explains why we divide by the factorial of each repeated group, using labels on the identical letters just as in the diagram above.
Warning
Dividing by the wrong thing. For NYABARONGO you divide by , not by and not by . Each repeated letter contributes its own factorial, and the factorials are multiplied.
Tip
Before calculating, write each letter with its count, for example N2 Y1 A2 B1 R1 O2 G1. The total of the counts is , and every count greater than 1 gives a factorial in the denominator.
Practice
Important
unlike objects in a row: . With repeated groups of sizes : . Together: make a block. Apart: total minus together.
Sources and credits
Text, diagram, worked examples and exercises: Written by Ganzaa.
Video: Permutations: how do we account for repetitions?, Eddie Woo, embedded from YouTube.
