Permutations PDF

Permutations Example Alan, Cassie, Maggie, Seth and Roger want to take a photo in which three of the five friends are lined up in a row. How many different photos are possible? AM C AM S AM R ACS ACR ACM ASM ARM ASC ARC...

Permutations Example Alan, Cassie, Maggie, Seth and Roger want to take a photo in which three of the five friends are lined up in a row. How many different photos are possible? AM C AM S AM R ACS ACR ACM ASM ARM ASC ARC CAM M AS M AR CAS CAR CM A M SA M RA CSA CRA M AC SAM RAM SAC RCA M CA SM A RM A SCA RAC ASR M SR M CR M CS CRS ARS M RS M RC M SC CSR SAR SM R RM C CM S RCS SRA SRM RCM CSM RSC RSA M RS CRM SM C SCR RAS M SR CM R SCM SRC 60, via an exhaustive (and exhausting!) list Permutations Easier, using multiplication principle: 5 options for the person on the left, and once we’ve chosen who should stand on the left, 4 options for the position in the middle and once we’ve filled both those positions, 3 options for the person on the right. This gives a total of 5 × 4 × 3 = 60 possibilities. We have listed all Permutations of the five friends taken 3 at a time. P(5, 3) = 60 Permutations A permutation of n objects taken k at a time is an arrangement of k of the n objects in a specific order. The symbol for this number is P(n, k). Remember: 1. A permutation is an arrangement or sequence of selections of objects from a single set. 2. Repetitions are not allowed. Equivalently the same element may not appear more than once in an arrangement. (In the example above, the photo AAA is not possible). 3. the order in which the elements are selected or arranged is significant. (In the above example, the photographs AMC and CAM are different). Permutations Example Calculate P(10, 3), the number of photographs of 10 friends taken 3 at a time. P(10, 3) = 10 · 9 · 8 = 720. Note that you start with 10 and multiply 3 numbers. A general formula, using the multiplication principle: P(n, k) = n · (n − 1) · (n − 2) · · · (n − k + 1). Note that there are k consecutive numbers on the right hand side. Permutations Example In how many ways can you choose a President, secretary and treasurer for a club from 12 candidates, if each candidate is eligible for each position, but no candidate can hold 2 positions? Why are conditions 1, 2 and 3 satisfied here? P(12, 3) = 12 × 11 × 10 = 1, 320. Condition 1 is satisfied because we have a single set of 12 candidates for all 3 positions. Condition 2 is satisfied because no one can hold more than one position. Condition 3 is satisfied because being president is different than being treasurer or secretary. Permutations Example You have been asked to judge an art contest with 15 entries. In how many ways can you assign 1st , 2nd and 3rd place? (Express your answer as P(n, k) for some n and k and evaluate.) P(15, 3) = 15 · 14 · 13 = 2, 730. Example Ten students are to be chosen from a class of 30 and lined up for a photograph. How many such photographs can be taken? (Express your answer as P(n, k) for some n and k and evaluate.) P(30, 10) = 30 · 29 · 28 · 27 · 26 · 25 · 24 · 23 · 22 · 21. Note 30 − 10 = 20 and we stopped at 21. P(30, 10) = 109, 027, 350, 432, 000 Factorials Example In how many ways can you arrange 5 math books on a shelf? P(5, 5) = 5 · 4 · 3 · 2 · 1 = 120 The number P(n, n) = n · (n − 1) · (n − 2) · · · 1 is denoted by n! or “n factorial”. n! counts the number of ways that n objects can be arranged in a row. n! grows fast: 1! = 1, 2! = 2, 2! = 6, 4! = 24, 5! = 120, 6! = 720, 7! = 5, 040, 8! = 40, 320, 9! = 362, 880, 10! = 3, 628, 800,... 59! ≈ 1080 (roughly the number of particles in the universe) Factorials We can rewrite our formula for P(n, k) in terms of factorials: n! P(n, k) =. (n − k)! Example (a) Evaluate 12! (b) Evaluate P(12, 5). 12! = P(12, 12) = 12 · 11 · · · 2 · 1 = 479, 001, 600. 12! 479,001,600 P(12, 5) = 7! = 5,040 = 95, 040. Factorials Example In how many ways can 10 people be lined up for a photograph? 10! = P(10, 10). Example How many three letter words (including nonsense words) can you make from the letters of the English alphabet, if letters cannot be repeated? (Express your answer as P(n, k) for some n and k and evaluate.) P(26, 3) = 15, 600. Permutations of objects with some alike Example How many words can we make by rearranging the letters of the word BEER? The set {B, E, E, R} = {B, E, R} but we really have 4 letters with which to work. So let us start with the set {B, R, E , E }. We arrange them in 4! = 24 ways: BREE BERE BEER RBEE REBE REEB EBRE EBER EEBR ERBE EREB EERB BREE BERE BEER RBEE REBE REEB EBRE EBER EEBR ERBE EREB EERB If we can’t tell the difference between E and E (they are both just E), then the words group into pairs, e.g., EEBR and EEBR group together — both are the word EEBR. Thus the number of different words we can form by rearranging the letters must be 4! 4!/2 = 2! Note that 2! counts the number of ways we can permute the two E’s in any given arrangement. Permutations of objects with some alike In general the number of permutations of n objects with r of the objects identical is n! r! n! Note that = P(n, n − r). r! Permutations of objects with some alike Example How many words (including nonsense words) can be made from rearrangements of the word ALPACA? 6! 720 = = 120. There are 6 letters in ALPACA and one of 3! 6 them, 'A' is repeated 3 times. Example How many words can be made from rearrangements of the word BANANA? {B, A, N, A, N, A} = {A, B, N }. The 'A' is repeated 3 times. The 'N' is repeated 2 times. The 'B' is repeated once. 6! Hence the answer is = 60. 1! · 2! · 3! Permutations of objects with some alike Suppose given a collection of n objects containing k subsets of objects in which the objects in each subset are identical and objects in different subsets are not identical. Then the number of different permutations of all n objects is n! , r1 ! · r2 ! · · · rk ! where r1 is the number of objects in the first subset, r2 is the number of objects in the second subset, etc. Note that if you make the collection of objects into a set, the set has k elements in it. Note that for a subset of size 1, we have 1! = 1, so this formula is a generalization of the previous one. Permutations of objects with some alike Example How many words can be made from rearrangements of the letters of the word BOOKKEEPER? 10! = 151, 200. 1! · 3! · 2! · 2! · 1! · 1! There are 10 letters in BOOKKEEPER. In alphabetical order, B ↔ 1, E ↔ 3, K ↔ 2, O ↔ 2, P ↔ 1, R ↔ 1. Note that the total number of letters is the sum of the multiplicities of the distinct letters: 10=1+3+2+2+1+1. Taxi cab geometry In how many ways can a taxi drive from A to B, going the least possible number of blocks (nine)? As sB Two possible routes — SSSSEEEEE in red and ESSEEESES in blue — are shown. Taxi cab geometry To go using the least number of blocks, the cab must always go South (S) or East (E), and in total must use 4 S’s and 5 E’s. Any rearrangement of SSSSEEEEE gives a valid route, and there are 9! 4!5! such rearrangements. Taxi cab geometry Example A streetmap of Mathville is given below. You arrive at the Airport at A and wish to take a taxi to Pascal’s house at P. The taxi driver, being an honest sort, will take a route from A to P with no backtracking, always traveling south or east. As Cs sV sP Taxi cab geometry As Cs sV sP (a) How many such routes are possible from A to P? You need to go 4 blocks south and 5 blocks east for a total of 9 blocks so the number of routes is 9! 9·8·7·6 = = 9 · 2 · 7 = 126. 4! · 5! 4·3·2·1 Taxi cab geometry As Cs sV sP (b) If you insist on stopping off at the Combinatorium at C, how many routes can the taxi driver take from A to P? This is really two taxicab problems combined with the Multiplication Principle. The answer, in words, is ’the number of paths from A to C’ times ’the number of paths 4! from C to P’. The first is = 6 and the second is 2! · 2! 5! = 10 so the answer is 6 · 10 = 60. 2! · 3! Taxi cab geometry As (c) If wish to stop off at both the combinatorium at C and the Venni- Cs tarium at V, how many routes can sV your taxi driver take? sP This is three taxicab problems. The answer, in words, is ’the number of paths from A to C’ times ’the number of paths from C to V’ times ’the number of paths from V to 4! 3! P. The first is = 6, the second is = 3 and the 2! · 2! 1! · 2! 2! third is = 2 so the answer is 6 · 3 · 2 = 36. 1! · 1! Taxi cab geometry As (d) If you wish to stop off at ei- Cs ther C or V(at least one), how many routes can the taxi driver take? sV sP This problem involves both taxis and the Inclusion-Exclusion Principle. Suppose C denote the set of all paths from A to P that go through C and that V denotes the set of all paths from A to P that go through V. The number we want is n(C ∪ V ) since C ∪ V is the set of all paths which go through C or V. Taxi cab geometry As Suppose C denotes the set of all paths from A to P that go through C and that V denotes the set of all paths from A to P that go through V. Cs The number we want is n(C ∪ V ) since C ∪ V is the set sV of all paths which go through C or V. sP We have already computed n(C) = 60. For n(V ) we have 7! 2! 7·6·5 n(V ) = · = · 2 = 70. 3! · 4! 1! · 1! 6 We still need n(C ∩ V ) but C ∩ V is the set of all paths which go through both C and V and we have already computed this: n(C ∩ V ) = 36. Hence n(C ∪ V ) = 60 + 70 − 36 = 94 Taxi cab geometry Example Christine, on her morning run, wants to get from point A to point B. A D B (a)How many routes with no backtracking can she take? (b) How many of those routes go through the point D? (c) If Christine wants to avoid the Doberman at D, how many routes can she take? Taxi cab geometry A (a)How many routes with no backtracking can she take? (b) How many of those routes go through the D point D? (c) If Christine wants to avoid the Doberman at D, how many routes can she take? B (5 + 7)! (a) 5! · 7! (3 + 4)! (2 + 3)! (b) · 3! · 4! 2! · 3!   (5 + 7)! (3 + 4)! (2 + 3)! (c) − · 5! · 7! 3! · 4! 2! · 3!