Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 9 page Class Notes was uploaded by Chaya Botsford II on Monday October 12, 2015. The Class Notes belongs to MAD 2104 at Florida Atlantic University taught by Jorge Viola-Prioli in Fall. Since its upload, it has received 43 views. For similar materials see /class/221637/mad-2104-florida-atlantic-university in Mathematics Discrete at Florida Atlantic University.
Reviews for Honors Discrete Mathematics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/12/15
8FACTORIAL Recall that nPk the falling factorial stands for nn1n 2 n k1 A special case occurs when kn in this case nPn nn 1n 2 321 We will not write it as nPn since have a special name and symbol for this product DEFINITION The factorial of n is the number nn 1n 2 321 to be denoted henceforth by n According to the results of our previous section n is the number of nlists of n different objects In other words n number of permutations of n distinct objects J Viola Prioli Hence three people can stand in line in 3 ways Since 3 321 6 we have 6 different arrangements Wehavell1 22 36 424 5120etc We complete our list by de ning 0 1 ILLUSTRATIONS a How many lists of length 5 from a pool of 00123 if the two zeros are placed next to each other Solution To avoid misunderstandings we can think of a bag with ve balls two numbered with 0 one with 1 one with 2 and one with 3 J Viola Prioli We can proceed in two different ways For our rst approach we can think ofthe two zeros as an entity Thus we are permuting 4 different objects the pair 00 and the numbers 1 2 and 3 Thus the answer is 4 24 A different attack would be to think of tasks place the two zeros together we have four ways 0 O O O O O and O O and proceed then to ll the other spots with 12 3 The rst empty spot can be lled in 3 ways the second one in 2 ways the nal spot in 1 way By the FCP the total number of arrangements equals 4 x 3 x 2 x124 b A Boy a Girl a Cat and a Dog stand in line In how many ways can they do so ifthe pets must not be next to each other Solution We can count the ways according to where the cat stands J Viola Prioli Case 1 C The second spot can be occupied by B or G but not by D 50 two choices to ll the second spot The third spot likewise can be lled in to ways Finally the remaining spot is occupied in only one way By the FCP our case 1 can be completed in 2 x 2 x 1 ways that is 4 ways Case 2 C In this case D must occupy the rightmost position read the statement please 50 we must consider C D This is completed by placing B and G then in 2 ways 50 case 2 takes 2 ways Case 3 C Totay similar to case 2 So 2 more ways Case 4 C Totally similar to case 1 So 4 more ways We have considered all the possible arrangements so we must add the numbers to get the total That is the answer is 12 J Viola Prioli c A bag contains ve balls numbered 0 1 1 2 and 3 Find in how many ways they can be arranged in a line ifthe rst two balls must add up to 2 Solution We list the possible arrangements 2 O we must ll them with objects from the pool 113 Careful here they are not distinct elements We have 3 ways according to where the ball numbered 3 is placed 0 2 as before We have 3 more ways none of them has been counted above since the lists will differ in the rst entry to begin with 1 1 we count the permutations of O 2 3 that is 3 6 wa 5 Having analyzed all the cases we conclude that there are 12 different arrangements satisfying the condition ofthe problem J Viola Prioli Pose to understand why in Problem c the reasoning in the third case differs from those ofthe previous cases Continuing with the factorial we notice that n increases quite rapidly with values of n To have an idea ofthat magnitude let us compute the number of zeros at the end of 20 Since each zero comes from multiplying a 2 and a 5 and no other way count the pairs of 2 and 5 in 20 1 2 3 4 56 7 8 9 Q11 1213 14 g 16 17 18 19 Q There are only four 5 s and more than four 2 s we need only four to match with the ves Hence there are four zeros at the end of 20 If we address the same question this time with 15 we may be interested in entering 15 into a calculator The answer will be 1216451004 x 1017 This number ends in eight zeros see why but recall that the answer given by the calculator is only an approximation to the true value So how many zeros at the end of 15 Exercise J Viola Prioli Since the computation of factorials involve products it is useful to introduce a symbol to simplify the notation kn We denote by nak the product a1 x a2 x x an k1 Observe that k the dummy variable can be replaced by any other letter other than n which indicates the upper limit for the range of k Thus kn n k k1 ILLUSTRATIONS a k1102k11gtlt3gtlt5gtlt7gtlt x17x19x21 k0 J Viola Prioli b Gk 17 12 7 2 3 8 m 68544 k 2 cl Compute k100 k1 J Viola Prioli DISCUSSION 1 Exercise 89 Can you exhibit 7 consecutive composite numbers 2 The factorials increase quite rapidly How large is the difference between two factorials To answer this question prove the following n n l is a multiple ofn 12 J Viola Prioli