Class Notes (810,913)
CSCA67H3 (56)
Lecture

# Week 8 - Counting with Repetitions.pdf

13 Pages
475 Views

School
University of Toronto Scarborough
Department
Computer Science
Course
CSCA67H3
Professor
Anna Bretscher
Semester
Fall

Description
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 ﬂavours 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 inﬂuencing modern economics and social sciences. ▯ Invented Pascal’s Triangle in his “Treatise on the Arithmetic Trian- gle”. Pasc
More Less

Related notes for CSCA67H3

OR

Don't have an account?

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.