Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 9 page Class Notes was uploaded by Dino Corwin 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 15 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
7LISTS A set is a collection of objects called its elements usually denoted by means of curly brackets When denoting a set like 5 1 2 a the order is irrelevant and repetitions are not allowed Thus 5 above has 4 different elements The set 123 equals 321 and 312 However 1223 makes no sense In a set the elements can be of a different nature More often than not one wishes to considers collections in which objects are repeated Thus we need a concept different from that of a set A list is a nite ordered sequence of objects that is usually denoted by writing them between parentheses Therefore in a quotit the order is crucial and the elements can be repeated J Viola Prioli Moreover as in sets the elements can be of a different nature The number of entries in a list is called the length of the list Therefore 0 1 O O 1 is a list of length ve and 2 7 a John a a is a list of length six Two lists are equal if they have the same length and the same corresponding entries A list of length two is simply called an ordered pair A list of length three is referred to as an ordered triple In what follows we calculate the number of pairs and triples J Viola Prioli What is the number of ordered pairs if entries can be taken from a set of size n Since we are counting we may take the set to be 1 2 n without loss of generality Now it is easy to write down all the pairs 1 1 1 2 1 n 2 1 2 2 2 n 3 1 3 2 3 n n 1 n 2 n n J Viola Prioli Clearly they are all different and we have exhausted them all The number of ordered pairs is thus n2 How many ordered pairs a b are there if a comes from a pool of m distinct elements and b from a pool of n distinct elements In this case the arrangement looks like 1 1 1 2 1 n 2 1 2 2 2 n 3 1 3 2 3 n m 1 m 2 m n thus the answer is mxn J Viola Prioli We are ready to state and prove the following basic result that is Theorem 72 in the textbook FUNDAMENTAL COUNTING PRINCIPLE f task A can be performed in m different ways and after A has been completed task B can be performed in n different ways then the combined task A followed by task B can be performed in exactly mxn ways Proof We can identify quotA followed by Bquot with ordered pairs ab We have m choices for a and n choices for b so mxn pairs according to our previous computation We emphasize that the answer is not m n but mxn With the tool afforded by the Fundamental Counting Principle FCP we can next analyze longer lists J Viola Prioli How many ordered triples a b c are there if a has m different choices b has n different choices and c has k different choices To manufacture ordered triples a b c we can think of two tasks Task A construct the pair ab Task B complete the triple a b c For A we have mxn choices Once A has been completed we insert the entry c in k ways By the FCP we have mxn x k different ways We conclude that there are mxnxk ordered triples Thus there are 43 triples a b c if the entries come from 1 2 3 4 J Viola Prioli By repeated application of the FCP we have the following If there are 5 tasks to be considered one after the other and after taskj1 has been concluded the taskj can be performed in nj ways then the sequence of tasks can be completed in n1 x n2 x x nS TIP Counting problems involving lists can be complicated however they become manageable if we think in terms of tasks Let us discuss exercises 75 and 77 DEFINITION A binary string of length k also called a kbinary string is a list of length k whose entries come from 0 1 In brief quotis a list of O and 1 of length kquot Therefore 0 O 1 is a 3binary string and so is 1 1 1 J Viola Prioli Since each entry has 2 choices our Corollary above shows that there are 2n binary strings of length n The number of n length binary strings is 2n What happens if we do not allow repetitions More precisely suppose we must compute the number of lists of length k taken from a pool of n different objects if repetitions of the entries are not allowed The rst entry will have n choices the second entry will have only n l choices the third entry must be chosen from n 2 objects etc As a result the number of different arrays will be n x n l x n 2 x x n k1 This number so constructed is called the falling factorial usually indicated in calculators by the symbolnPk Notice that nPk is the product of k consecutive integers beginning with n in decreasing order Of course in all these cases n 2 k gt O J Viola Prioli For instance 7P5 7 x 6 x 5 x 4 x 3 2520 and nP1 n for all n gt 0 We can discuss now Exercise 711 and others J Viola Prioli