Math 111, section 6.4 Permutations and Combinations notes by Tim Pilachowski The Multiplication Principle was introduced in section 6.3: Suppose a task T1 can be peformed in N1 ways, a task T2 can be peformed in N2 ways, … and finally, a task Tm can be peformed in Nm ways. Then the number of ways of performing the tasks T1, T2, … , Tm is given by the product N1 times N2 times … times Nm. The Examples used in Lecture 6.3 were carefully chosen so that successive tasks were independent, i.e., so that the first event had no influence on the next. The first die rolled did not affect the second. In the club elections, no one person was a candidate for more than one office. Farnsworth’s choice of screen size did not affect his choice of CPU speed. Letters and numbers in the license plates could be used more than once. But what if the result of the first event does have an effect on the outcome of the second? Example A-1. Eddington has three blocks to play with: red, yellow, and blue. If he lays them out into a line one at a time, how many designs can he create? Example B-1. Eddington has six blocks to play with: purple, red, orange, yellow, green and blue. If he lays them out into a line one at a time, how many designs can he create? Example C-1. Eddington has ten blocks to play with: purple, red, orange, yellow, green, blue, white, black, gray, and brown. If he lays them out into a line one at a time, how many designs can he create? This type of arrangement, in which the order of objects or events makes a difference, e.g. RYB ≠ RBY, is called a permutation. For our text and for this class, we will assume that there is no repetition in a permutation, e.g. Edd could not and would not have two red blocks side by side because he picks a block and does not put it back. The Multiplication Principle applied to a permutation involves what is called a factorial. For any positive integer n, “n factorial” is written and defined as ()()()()()12321!K−−= nnnn and by definition 0! = 1. Notes on factorials:Example A-1 revisited. Eddington has three blocks to play with: red, yellow, and blue. If he lays two of them out into a line one at a time, how many designs can he create? Example B-1 revisited. Eddington has six blocks to play with: purple, red, orange, yellow, green and blue. If he lays three of them out into a line one at a time, how many designs can he create? Example C-1 revisited. Eddington has ten blocks to play with: purple, red, orange, yellow, green, blue, white, black, gray, and brown. If he lays four of them out into a line one at a time, how many designs can he create? The process developed in Examples A-1 through C-1 can be generalized into the following formula for the number of permutations of n distinct objects taken r at a time: ( )( )!!,rnnrnP−= . Other notations that are used and you may encounter include rnP and rnP . Example D-1. Eddington has fifteen blocks to play with, each one a different color. How many ways can he pick up just one? How many ways can he line up all fifteen? Example A-2. Eddington has three blocks to play with: red, yellow, and blue. If he picks up two of them at the same time, how many ways can he choose blocks? Example B-2. Eddington has six blocks to play with: purple, red, orange, yellow, green and blue. If he picks up three of them at the same time, how many ways can he choose blocks?Example C-2. Eddington has ten blocks to play with: purple, red, orange, yellow, green, blue, white, black, gray, and brown. If he picks up four of them at the same time, how many ways can he choose blocks? The process developed in Examples A-2 through C-2 can be generalized into the following formula for the number of combinations of n distinct objects taken r at a time: ( )()( )!!!!,,rnrnrrnPrnC−== . Other notations that are used and you may encounter include rn which your text has also, rnC and rnC . Theory: Example D-2. Eddington has fifteen blocks to play with, each one a different color. How many combinations of 1 block are there? How many combinations of 15 blocks are there? Your textbook exercises for day 1 of section 6.4 ask you to calculate values for various versions of P(n, r) and C(n, r). Note that for something like P(20, 24) and C(17, 18) the correct answer is “not possible”. Why? Example E-1. How many arrangements of 3 digits (repeated digits allowed) are there, chosen from the ten digits 0 to 9 inclusive? How many permutations of 3 different digits (i.e., no repeats) are there, chosen from the ten digits 0 to 9 inclusive? How many combinations of 3 different digits are there, chosen from the ten digits 0 to 9 inclusive?Example E-2. How many arrangements of 4 letters (repeated letters allowed) are there, chosen from the twenty six letters of the alphabet? How many permutations of 4 different letters (i.e., no repeats) are there, chosen from the twenty six letters of the alphabet? How many combinations of 4 different letters are there, chosen from the twenty six letters of the alphabet? Examples E-1 and E-2 identified whether the situation was a permutation or combination, with or without repeated elements. In word problems it’s not always so easy. Example F. a) In Arithmetic, addition is both commutative and associative, that is numbers can be rearranged and regrouped in any way and the answer will still be the same. Is addition more like a combination or permutation? b) In Arithmetic, division is neither commutative nor associative. It makes a difference whether one is calculating “p divided by q” or “q divided by p”. Is division more like a combination or permutation? Example G. a) The cook at Pappy’s Restaurant makes a pizza by first rolling out and stretching the dough for the crust, then spreading out the sauce, then adding cheese and toppings. Is making a pizza more like a combination or permutation? b) The cook at Pine Tree Café D’ makes sausage stew by throwing all of the ingredients into a pot and letting it simmer for four hours. Is making stew more like a combination or permutation? Example H. a) Harold Hill puts his knick knacks on a shelf according to whatever whim hits him at the moment, and is likely to move them around periodically. Is Harold’s method an example of a combination or permutation? b) Marian puts books on the shelf in the town’s library, arranging them by using