Clear Notion
Login

Concepts

Read through concept notes with worked explanations and diagrams, chapter by chapter.

Concept 02 / 09Permutations and Combinations

Permutations: Arrangements with Distinct and Identical Objects and Restrictions

The formula nPr = n!/(n - r)!, arrangements with repetition, arrangements of objects that are not all distinct (n!/(p! q! r!)), and the standard restriction techniques: fixing positions, the 'together' block method, the gap method for 'never together', and rank of a word in dictionary order.

Figure 1
A permutation is an arrangement, where order matters. The number of ways to arrange rr objects chosen from nn distinct objects, without repetition, is nPr=n(n−1)(n−2)⋯(n−r+1)=n!(n−r)!^{n}P_{r} = n(n - 1)(n - 2)\cdots(n - r + 1) = \frac{n!}{(n - r)!}, because the first position has nn choices, the second n−1n - 1, and so on for rr positions. In particular all nn objects can be arranged in nPn=n!^{n}P_{n} = n! ways. If repetition is allowed, each of the rr positions has nn choices, giving nrn^{r}. Objects that are not all distinct. If nn objects include pp identical of one kind, qq identical of another, rr of a third, and the rest distinct, the number of arrangements is n!p! q! r!\frac{n!}{p!\,q!\,r!}. Reason: if we temporarily label the identical objects to make them distinct, there are n!n! arrangements, but each genuine arrangement has been counted p! q! r!p!\,q!\,r! times (once for every way of permuting the labels within each kind). Dividing removes the overcount. This 'count with labels, then divide by the symmetry' idea is one of the most useful in combinatorics. Example: the letters of MISSISSIPPI (1111 letters: M once, I four times, S four times, P twice) can be arranged in 11!4! 4! 2!=34650\frac{11!}{4!\,4!\,2!} = 34650 ways. Standard restriction techniques. Fixed positions: place the restricted objects first, then arrange the rest. Always together: glue the objects that must be together into a single block, arrange the block with the other objects, then multiply by the number of internal arrangements of the block. For example, arranging 55 boys and 33 girls with all girls together: 6!6! arrangements of 55 boys plus one block, times 3!3! inside the block, giving 43204320. Never together (no two adjacent): use the gap method shown in the figure. Arrange the unrestricted objects first; they create gaps between and at the ends. Place the restricted objects into distinct gaps. With mm unrestricted objects there are m+1m + 1 gaps. Note that 'not all together' is different from 'no two together': 'not all together' is simply total minus 'all together'. Relative order fixed: if certain kk objects must appear in a specified order (say A before B before C), arrange everything freely and divide by k!k!, because each of the k!k! orders of those objects is equally common. Dictionary rank. To find the position of a word among all arrangements of its letters in alphabetical order, go letter by letter: at each position, count the arrangements that start with the same prefix but a smaller letter in this position, add them up, and add 11 for the word itself. With repeated letters, each count uses the n!p! q!\frac{n!}{p!\,q!} formula for the remaining letters. Key Takeaways: - nPr=n!(n−r)!^{n}P_{r} = \frac{n!}{(n - r)!}; with repetition, nrn^{r}. - nn objects with p,q,rp, q, r alike: n!p! q! r!\frac{n!}{p!\,q!\,r!}. - Together: treat as one block, then multiply by the block's internal arrangements. - Never together: arrange the others, then choose distinct gaps; mm objects create m+1m + 1 gaps. - 'Not all together' = total −- 'all together', which is different from 'no two together'. - Fixed relative order of kk objects: divide by k!k!. - Pitfall: in the gap method, forgetting the two end gaps. Brain-Teaser 1: In how many arrangements of the letters of ARRANGE do the two R's not come together? Solution: ARRANGE has 77 letters: A twice, R twice, N, G, E. Total arrangements: 7!2! 2!=1260\frac{7!}{2!\,2!} = 1260. With the two R's together, treat RR as one block: 66 units with A repeated twice, giving 6!2!=360\frac{6!}{2!} = 360 (the block's internal order is fixed, since the R's are identical). So the answer is 1260−360=9001260 - 360 = 900. Alternatively, by the gap method, arrange A, A, N, G, E in 5!2!=60\frac{5!}{2!} = 60 ways, creating 66 gaps, and choose 22 gaps for the identical R's in (62)=15\binom{6}{2} = 15 ways: 60×15=90060 \times 15 = 900. The two methods agree. Brain-Teaser 2: Find the rank of the word MOTHER among all arrangements of its letters in dictionary order. Solution: The letters in order are E, H, M, O, R, T. First letter: words starting with E or H come before M: 2×5!=2402 \times 5! = 240. With M fixed, the second letter is O; letters smaller than O among the remaining E, H, O, R, T are E and H: 2×4!=482 \times 4! = 48. With MO fixed, the third letter is T; smaller remaining letters are E, H, R: 3×3!=183 \times 3! = 18. With MOT fixed, the fourth letter is H; smaller remaining is E: 1×2!=21 \times 2! = 2. With MOTH fixed, the fifth letter is E, and nothing smaller remains: 00. Sum: 240+48+18+2=308240 + 48 + 18 + 2 = 308, so MOTHER is the 309309th word. The final +1+1 accounts for the word itself. Brain-Teaser 3: How many 55-digit numbers divisible by 33 can be formed using the digits 0,1,2,3,4,50, 1, 2, 3, 4, 5 without repetition? Solution: A number is divisible by 33 iff its digit sum is. The six digits sum to 1515; leaving out one digit dd gives sum 15−d15 - d, divisible by 33 iff d=0d = 0 or d=3d = 3. Leaving out 00: digits 1,2,3,4,51, 2, 3, 4, 5, all usable in the first place, giving 5!=1205! = 120. Leaving out 33: digits 0,1,2,4,50, 1, 2, 4, 5; the first digit cannot be 00, giving 5!−4!=965! - 4! = 96. Total: 216216. The divisibility rule converts a condition on the number into a condition on which digits are chosen, which splits the count into clean cases.

Practice this concept

Free · no account required · instant solutions

Permutations: Arrangements with Distinct and Identical Objects and Restrictions — DPP

4 questionsSee the solution the moment you answer

Practice