Week 8 - Counting with Repetitions.pdf

13 Pages
Unlock Document

University of Toronto Scarborough
Computer Science
Anna Bretscher

Counting With Repetitions The genetic code of an organism stored in DNA molecules con- sist of 4 nucleotides: Adenine, Cytosine, Guanine and Thymine. ▯ It is possible to sequence short strings of molecules. ▯ One way to sequence the nucleotides of a longer string of DNA is to split the string into shorter sequences. ▯ A C-enzyme will split a DNA-sequence at each “C”. This means that each fragment will end at a C except possibly the last fragment. ▯ Similarly for A-enzymes, G-enzymes and T-enzymes. ▯ If the original nucleotide is split on each of C, A, G and T then it can be sequenced as it is most likely a unique sequence that can be constructed by each of the four sets of fragments. 1 Example. Given a 20-nucleotide string split at the Cs, one might have the fragments: AC, AC, AAATC, C, C, C, TATA, TGGC Q. How many different 20-nucleotide strings could have given rise to the above set of fragments? In other words, how many different arrangements are there of these fragments? A. 2 Theorem. Given n objects, with1r of type 12 r of type 2, ..., rm of type m where r1+ r 2 ::: + r m = n then the number of arrangements of the n objects, denoted by P(n;r 1r 2:::;rm) is: ▯n▯▯ n ▯ r ▯▯n ▯ r ▯ r ▯ ▯n ▯ r ▯ r ▯ ▯▯▯ ▯ r ▯ = 1 1 2 ▯▯▯ 1 2 m r1 r2 r3 rm Q. What does this formula simplify to? A. 3 Proof. n! P(n;r ;1 ;2::;r )m= r1!r2!:::rm! ▯ Convert the problem into something we can already solve. ▯ Suppose all objects are distinct. How many permutations are there? th ▯ Consider the i type. It is repeatedir times. ▯ Add the subscripts 1;2;:::;r io make them unique. Example. Let our set of objects be the letters fb;a;a;a;n;ng. We can make the as and ns unique as follows: a ;a1;a 2 3 n 1n 2 Q. Number of permutations of fb;a 1a ;2 ;3 ;n1g?2 A. We can think of this as the number of ways to arrange fb;a;a;a;n;ng ▯ . Q. How do we say this mathematically? A. 6! = ▯?? 4 Q. Suppose we have b;a;a;n;n;a. What are the different ways to arrange the as? A. Q. How many ways to arrange the ns for each arrangement of as? A. Resulting in: ▯ Generally, for the type, we have ways to arrange the objects. Therefore: n! = n! = ▯ Rearranging gives: P(n;r 1r 2:::;r m = 5 Selections With Repetitions Example. While shopping at the St. Lawrence market, you decide to buy half a dozen bagels. There are three flavours to choose from. Q. How many different ways can you select your 6 bagels? A. Rephrase as an arrangement problem. Sesame Poppy Seed Plain xx xxx x Q. How is this an arrangement problem? A. Q. How can we also think of this as a selection problem? A. Let n be the number of choices, r the number of items selected. Then 8 = r + (n ▯ 1) and we are choosing r = 6. This results in: 6 Theorem. Given r objects and n types of objects to choose from, the number of selections with repetitions is: ▯ ▯ r+ ( n ▯ 1) r Proof. Simply generalize the arguments above. Example. How many ways are there to select a committee of 15 politicians from a room full of ▯ indistinguishable Democrats, ▯ indistinguishable Republicans and ▯ indistinguishable Independents if every party must have at least two members on the committee? Solution. 7 Pascal’s Triangle Blaise Pascal [1623-1662] was a French mathematician, physi- cist, inventor, writer and philosopher. ▯ As a teenager, he invented the mechanical calculator. ▯ He collaborated with Pierre de Fermat in Probability Theory influencing modern economics and social sciences. ▯ Invented Pascal’s Triangle in his “Treatise on the Arithmetic Trian- gle”. Pasc
More Less

Related notes for CSCA67H3

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.