Class Notes
(810,913)

Canada
(494,374)

University of Toronto Scarborough
(30,849)

Computer Science
(300)

CSCA67H3
(56)

Anna Bretscher
(30)

Lecture

# Week 8 - Counting with Repetitions.pdf

Unlock Document

University of Toronto Scarborough

Computer Science

CSCA67H3

Anna Bretscher

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