University of Toronto at Scarborough CSCA67 / MATA67Discrete Mathematics, Fall 2016 Exercise #7: Arrangement with Repetition Due: November 18, 2016 at 11:59 p.m. This assignment is worth 3% of your final grade. Warning: Your electronic submission on MarkUs affirms that this exercise is your own work and no one else's, and is in accordance with the University of Toronto Code of Behaviour on Academic Matters, the Code of Student Conduct, and the guidelines for avoiding plagiarism in CSCA67 / MATA67. This exercise is due by 11:59 p.m. November 18. Late exercises will not be accepted. [5] 1. In lecture we introduced the topic of arrangement with repetition by counting how many different 20-nucleotide molecules could give rise to the C-enzyme fragmentation: AC, AC, AAATC, C, C, C, TATA, TGGC (a) Although it seems we must consider all possible arrangements of 8 fragments when counting, we actually need only consider arrangements of 7 of the fragments. Why? (b) We solved this problem as a product of combinations, starting with placing the 3 C fragments in 3 of 7 possible positions. We then placed the 2 AC fragments, followed by the AAATC fragment and then the TGGC fragment. Show that the same count is obtained by placing the fragments in different ways (e.g., place the AC fragments first). How many different ways are there to place the fragments? [5] 2. Given n objects, with r1 of type 1, r2 of type 2, . . . , rm of type m, where r1 + r2 + + rm = n the formula for arrangement with repetition when considered as a product of combinations as in #1 above simplifies to: n! P (n; r1 , r2 , . . . , rm ) = r1 ! r2 ! rm ! In lecture we hinted how to prove this but we did not actually prove it. Complete the proof. Hint: Show the details of the cancellation between the denominator of the (i 1)-st combination and the numerator of the i-th combination in the product of combinations. [4] 3. You are stopping by Timmy's to buy 12 donuts. There are 4 varieties to choose from. You need to have at least one donut from each variety. How many different ways can you select your 12 donuts? (a) Count by arrangement with repetition. (b) Count by selection (combination). Page 1 of 2 pages. [3] 4. In a club with 12 members, (a) in how many ways can a committee of 3 be selected? (b) in how many ways can a president, secretary, and treasurer be appointed? [3] 5. In how many ways can six 3's and four 2's be arranged in a row so that the 2's are always apart? [total: 20 marks] Page 2 of 2 pages