Honors Discrete Mathematics
Honors Discrete Mathematics MAD 2104
Popular in Course
Popular in Mathematics Discrete
This 12 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 11 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.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/12/15
15PARTITIONS In our previous section we proved that the equivalence classes of any equivalence relation on a set A fragments A in a certain way their members are nonempty they are pairwise disjoint and their union is the original set A Those properties actually de ne what is called a partition ofthe set A DEFINITION A partition ofA is a collection P of subsets ofA each one called a part of P with three properties 1 the parts are non empty 2 the parts are pairwise disjoint ie different parts have empty intersection 3 the union ofall the parts is A ie every element ofA is in one part Graphically a partition ofA looks like a tiling ofA a mosaic REMARK a It should be emphasized that the parts need not be ofthe same size b There may be in nitely many parts in P c Parts may contain in nitely many elements d Do not confuse parts with partition Examples a A 2 can be partitioned with odd numbers and even numbers There are two parts b A 2 can be partitioned with positive integers 0 negative integers There are three parts c A N can be partitioned with O 123456789 1011121314 etc There are in nitely many parts each of them has nitely many elements all parts are of different sizes cl A N can be partitioned with 01 composite numbers prime numbers This partition has three parts one of them with two elements the other two with in nitely many elements How many partitions of a 3element set are there Say A a b c We have the following partitions Partition 1 abc Partition 2 a b c Partition 3 a b c Partition 4 a c b Partition 5 b c a In conclusion there are exactly ve partitions of a 3element set The tight link between equivalence relations and partitions is given next It shows that there is a onetoone correspondence between two different concepts THEOREM Every equivalence relation on a set A determines a partition of A Conversely every partition of A determines an equivalence relation on A Proof The rst statement has been proved in our previous section The parts ofthe partition are the equivalence classes As to the second statement suppose we are given a partition P of a set A We wish to de ne an equivalence relation on A by using the parts of the partition To that end declare aRb if a and b belong to the same part of the partition Analogy think ofthe world countries and declare two individuals related if they are citizens of the same country We must show that this relation R satis es the three properties of an equivalence relation Re exive let a E A By property 3 of partitions a belongs to some part of P Thus aRa Symmetric if aRb then a and b belong to a part C of P Then b and a belong to C Hence bRa Transitive assume aRb and bRc Thus there exists a part M such that a and b belong to M Likewise there exists a part N such that b and c belong to N Notice that then b belongs to both M and N Hence M and N are not disjoint Therefore M and N are not different Property 2 of partitions Hence MN and a and c belong to N Conclude that aRc TIP The importance of this theorem is that provides a great tool to construct equivalence relationsl Given A just take any partition of your liking Example Find the partition associated with congruence mod 4 in the set A 3 4 517 We have the parts given by the equivalence classes therefore 3 7 11 15 4 8 12 165 9 13 176 10 14 Observe that the parts are non empty pairwise disjoint and their union is A When all the parts of a partition have the same size we have PROPOSITION Let A be a nite set Assume P is a partition of A whose k parts are ofthe same size say m Then A k m Proof Obvious The book presents as an application of this result the computation of anagrams DEFINITION An anagram of a word is any rearrangement of its letters Therefore an anagram is just a permutation of the letters of a word If the word has n letters and they are all distinct then we know there are n anagrams For instance the anagrams of TALE are 4 ie 24 On the other hand the anagrams of TELL are TELL TLLE TLEL LLET LLTE LELT LETLETLL ELLT ELTL LTELLTLE that is only 12 It should be clear that an anagram is legitimate regardless of whether the resulting word appears or not in a dictionary The question which we have not considered yet in its generality is how many anagrams are there if some letters are repeated This question has a direct answer as we will provide a formula to nd the anagrams The argument will be presented with a particular word as an illustration However it should be appreciated that it works in general Take the word DISTRIBUTION it has 12 letters the repeated letters being I 3 times and T twice We anticipate that the number of anagrams will not be therefore 12 as with this number we will be over counting the anagrams But what is the over counting factor The idea of the proof is to a Let A set of all the anagrams of a particular word with 12 di 39erent letters Hence A12l b Partition A with k parts of the same size c Use the Proposition above so A k m d Verify that each part corresponds to one of the desired anagrams e Conclude that there are A m anagrams of DISTRIBUTION Of course as we proceed according to that scheme we must find the number m Observe that m is the over counting factor we have referred to before To begin with let us use subindexes quotlabelsquot to distinguish the repeated letters hence DISTRIBUTION becomes D 1 S T1 R 2 B U T2 l3 0 N This word has 12 anagrams Let A denote the set ofthese 12 anagrams De ne an equivalence relation on A as follows two anagrams in A are related if after the labels are removed they are the same word For instance the words Bl1D T12UT230 NR and BIZSD T23UT110 NR are related since theyboth reducetoBlSDTl UTIONR It is easy to see that this is an equivalence relation on A Moreover all the equivalence classes have the same size Let us show why this is true Take the equivalence class of a word in A say B 2 S D T2 3 U T11 O N R The words that are equivalent to this one are obtained by preparing twelve slots in which BSDUONR have xed positions B S D U 0 N R Let us proceed to ll the empty slots with 1 l2 and I3 we must ll 3 slots rst third fth which can be done in 3 ways With T1 and T2 we ll the remaining slots in 2 ways We have therefore 3 2 ways to complete the anagrams in the class of B 2 S D T2 3 U T1 l1 0 N R The same argument applies to any other class because we end up with exactly the same argument and computation So all the classes have the same sizeI equal to 3 2 Thus we can apply the previous proposition Accordingly A size ofa class x number of classes and therefore 12 3 2 x number of classes Since by counting each class we count an anagram of DISTRIBUTION we solve for the number of classes and obtain The number ofanagrams of DISTRIBUTION is x In general we have the following FORMULA FOR ANAGRAMS The number of different anagrams of a word of n letters is n divided by the product of the factorials of repeated letters Observe that we have found the over counting factor we mentioned before in the case of DISTRIBUTION the factor is 2 x 3 l Likewise the anagrams of TREAT are 60 and those of the word 2 14 MATHEMATICALLY are 2 x2 x2 x3 We may make use of the formula to solve similar problems when numbers are involved PROBLEMS a How many arrangements of the number 95304195 are there if we insist on keeping the 9 s in their positions Solution We must simply count the quotanagramsquot of 530415 50 the number is 6 7 60 2 b How many arrangements of the number 95304195 are there if we keep the 9 s together Solution 99 may occupy 7 different positions why For each of them we have as before 360 arrangements 50 the total number is 7 360 2520 c How many 10Iength binary strings are there with exactly 4 zeros Solution This reduces to counting the quotanagramsquot of O O O O 1 1 1 1 1 1 10 4 x6 Their number is OBSERVATION The textbook solves several problems in this section by resorting to the adequate use ofthe Proposition see above The dif culty lies in how to reduce complicated problems to a corresponding problem with equivalence relations However there is an alternative simpler way to solve them as we will be seeing in the next section
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'