Transcript Fundamental Principles of Counting

• How many ways are there to pass through city A where the
arrows represent one-way streets?
m roads
...
A
...
n roads
Answer: mn ways
• The counting principal: Suppose two experiments are to
be performed. If experiment 1 can result in any of m
possible outcomes and if for each of these outcomes of
experiment 1, there are n possible outcomes of experiment
2, then together there are mn possible outcomes of the two
experiments.
• The counting principal is also called the product rule.
Generalized Counting Principal
• If r experiments that are to be performed are such that the
first one may result in any of n1 possible outcomes, and if
for each of these n1 outcomes there are n2 possible
outcomes of the second experiment, and if for each of the
possible outcomes of the first two experiments there n3
possible outcomes of the third experiment, etc., then there
is a total of n1n 2 ...nr possible outcomes of the r
experiments.
• Example. How many different 7-place license plates are
possible if the first 3 places are to be occupied by letters
and the final 4 by numbers?
26  26  26  10  10  10  10  175,760,000.
• How many “words” of length three can be formed from the letters
a, b, c, d, and e if letters can be repeated?
Solution. There 5 choices for the first letter, 5 choices for the
second letter, and 5 choices for the third letter. Thus, the number
of “words” is 53 = 125.
• Theorem. The number of ordered arrangements of n distinct
objects of size r, 1  r  n, where repetition is allowed is given by
nr.
• Example. The latter theorem implies that b distinguishable balls
can be distributed into u distinguishable urns in ub ways. Note
that “distinguishable balls” can be interpreted as saying that the
__ __ ... __
balls are ordered.
b blanks to be filled with
labels 1 to u
Triplets of nucleotides in DNA
• A description of the structure of a DNA molecule can be found
at:
http://www.accessexcellence.org/RC/VL/GG/nucleotide2.html
• A nucleotide is represented by one of the letters in the set
{A,T,C,G}. A codon is defined to be a triplet of nucleotides.
The order of the nucleotides in a codon is significant, and
nucleotides can be repeated. These codons determine which
amino acid is to be made.
• How many different codons are possible? How does this
relate to the fact that there are only twenty amino acids?
• Given a collection of n distinct objects, any ordered
arrangement of these objects without repetition is called a
permutation of the collection. If only r of the objects,
1  r  n, are to be used in the ordered arrangement, then we
have an r-element permutation.
• How many ways of listing three letters chosen from the
collection a, b, c, d, and e are there? (Assume that no letter
can be repeated.) That is, we are asked to find the number of
permutations of size 3 for this collection of letters.
Solution. We have 5 choices for the first element in the
list. This leaves 4 choices for the second element.
Once
the first two are chosen, there are 3 choices
remaining for the third element. This qualifies
for the product rule since the number of choices only
depends on the stage of the process and not on the
particular letters which have been chosen. Thus, there
are (5)(4)(3) = 60 ways to list three letters.
• For any integer n  0, n factorial is defined by
0! = 1
n! = (n)(n-1)(n-2) …
(3)(2)(1), for n  1.
• Note that n! grows very rapidly. Beware of arithmetic
overflow if you try to calculate factorials explicitly on a
calculator.
• Theorem. The number of r-element permutations of n objects
is denoted by nPr and it equals
n!
(n)(n - 1)(n - 2)  (n - r  1) 
.
(n - r)!
• Corollary. If r = n, then we have that the number of
permutations of n objects is n!
• Example. Suppose 3 distinguishable balls are to be distributed
into 5 distinguishable urns in such a way that each urn contains at
most one ball. This can be done in 5!/2! ways.
___ ___ ___
3 blanks (for balls) to be filled with labels 1 to 5 (for
urns). This give us the permutations of 5 labels of size 3.
• Problem. How many distinct anagrams of the word BALL are
there? If we treat the two L’s as distinct objects, we have 4!
permutations of the four letters. However, the two L’s are not
distinct and some of the permutations will correspond to the
same anagram. In fact, there will be two permutations for every
distinct anagram. We have 2(number of distinct anagrams) =
(number of permutations of B, A, L1, L2). Thus, the number of
distinct anagrams = 4!/2 = 12.
• How many distinct anagrams are there of the word BANANA?
There are 6! permutations of the six letters where all letters are
considered distinct. However, the two N’s are not distinct and the
three A’s are not distinct. There are 2! ways to order the N’s and
there are 3! ways to order the A’s. Thus,
(2!)(3!)(Number of distinct anagrams of BANANA)
= (Number of permutations of B, A1, N1, A2 , N2 , A3).
• Theorem. If there are n objects with n1 of the first type, n2 of the
second type, …, and nr of an rth type, where n1 + n2 + … + nr = n,
then there are
n!
(n 1!)( n 2 !)  (n r !)
ordered arrangements of the given objects where objects of the
same type are indistinguishable. Note: These ordered
arrangements are again called permutations (with
indistinguishable objects)
• Recall that the number of permutations of n distinct objects
of size r is n!/(n-r)! If we don’t care about the order of the
objects chosen, then we are asking for the number of
subsets of size r chosen from the n objects. We see that
each such subset can be ordered in r! ways. Thus, we have
r!(numberof subsets of size r)  (numberof r - elementpermutations).
Such a subset of size r is also called a combination, and
the number of possible combinations of size r chosen from
n distinct objects is denoted by  n  or by nCr .
r 
 
• Theorem.
n
n!
  
, 0  r  n.
 r  r! (n - r)!
• Problem. How many thirteen card bridge hands chosen from
an ordinary deck of 52 cards are there? Since we don’t care
about the order in which the cards are received, we want the
number of combinations,  52  = 635,013,559,600.
13 
• In order to see a connection between the number of
permutations with two groups of indistinguishable objects
and 10  , suppose that we have ten objects lined up as
 4
a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 , a 8 , a 9 , a 10
and then we distribute 4 labels I (for “in the set”) and 6
labels N (for “not in the set”) in the ten spaces occupied by
the objects. We can count this as 10  or as permutations
 4
with indistinguishable objects
10!
.
(4!)(6!)
Of course, these two values are the same.
• In the expansion of the n terms (x+y)(x+y)(x+y)…(x+y), we
may choose x from n-i of the terms, and y from the remaining
i terms to form a xn-iyi. We don’t care about the order in
which the terms are chosen, so the number of ways to form
the term xn-iyi is  n  . Thus,
i 
 n  n 0  n  n -1 1
 n  0 n n  n  n -i n
(x  y)   x y   x y     x y    x y .
i 0  i 
0 
1 
n
The latter result is known as The Binomial Theorem and it
has a generalization called the Multinomial Theorem.
n
• Examples. (x  y)3  x3  3xy 2  3x 2 y1  y 3 .
(x  y)4  x 4  4x 3 y1  6x 2 y 2  4xy3  y 4 .
• The quantities
n
 
i 
are also called binomial coefficients.
Multinomial Coefficients
• If n1 + n2 + … + nr = n, we define


 n1 n 2
n
n3

n!
 
.
... n r  (n1!)(n 2!)...(n r !)
n


• As shown in the textbook, 

 n1 n 2 n 3 ... n r 
represents the number of possible divisions of n distinct
objects into r distinct groups of respective sizes n1, n2 , … nr.
n


• From previous work, we know that 

 n1 n 2 n 3 ... n r 
also represents a permutation. The connection between the
two interpretations can be made by considering r types of
labels for the n objects.
Using the multinomial coefficients.
• (x1+ x2+ x3)2 =
2
2
2

 2 0 0 
 0 2 0 
 0 0 2

 x1 x 2 x 3  
 x1 x 2 x 3  
 x1 x 2 x 3 
 2, 0, 0 
 0, 2, 0 
 0, 0, 2 
2
2
2  0 1 1

 1 1 0 
 1 0 1 

 x1 x 2 x 3  
 x1 x 2 x 3  
 x1 x 2 x 3
1, 1, 0 
1, 0, 1 
 0, 1, 1 
 x12  x 22  x 32  2x 1 x 2  2x 1 x 3  2x 2 x 3
• Problem. If 12 distinguishable balls are to be placed into 3
distinguishable urns in such a way that each urn has 4
balls, how many ways can this be done?
The number of integer solutions of equations
• Suppose we have n indistinguishable balls and r
distinguishable urns. How many ways are there to distribute
the balls into the urns (where some urns may be empty)?
This is readily seen to be equivalent to finding the number of
distinct nonnegative integer-valued vectors (x1, x2, ... , xr)
such that x1+ x2+ ... + xr = n.
• To solve this problem with “nonnegative” replaced by
“positive”, imagine that the n indistinguishable objects are
lined up and that we want to divide them into r nonempty
groups. To count the number of ways this can be done, we
select r – 1 of the n – 1 spaces between adjacent objects as
the dividing points (see below).
0  0  0 ...  0  0
Choose r  1 of thespaces  .
The number of integer solutions of equations, continued
• Theorem. There are
 n  1

 distinct positiveinteger - valued vectors
 r 1
(x1 , x 2 , ... , x r ) satisfyingx1  x 2  ...  xr  n.
• By making a simple change of variable we obtain:
Theorem. There are
 n  r  1

 distinct nonnegative integer - valued vectors
 r 1 
(x1 , x 2 , ... , x r ) satisfyingx1  x 2  ...  xr  n.
• Example. There are 2 positive integer-valued vectors
satisfying x1 + x2 = 3.
More balls and urns
• Suppose 12 indistinguishable balls are to be placed in 3
distinguishable urns with no urn left empty. The number of
ways to do this is 55. Do you see why?
• Suppose 12 indistinguishable balls are to be placed in 3
distinguishable urns with some urns possibly empty. There
are 91 ways to do this. Do you see why?
• Suppose an urn contains 11 distinguishable balls and a
sample of 3 balls is to be selected (without replacement).
How many different samples are there if
(a) the order in which the balls are drawn is important?
(b) the order in which the balls are drawn is not important?
• Tree diagrams provide a pictorial way to represent the
possible cases in a counting problem.
Two ways to count the same set of objects
• Often there are two ways to count the same set of objects and
this leads to an interesting result since the two ways must give
the same answer. This is known as a combinatorial argument.
• Problem. How many subsets of a given set with n elements are
there (include the empty set and the given set)?
• One way to count: Fill n blanks with one of two possible
labels, I or N, for “in the set” or “not in the set”: __ __ __ ... __
Clearly, there are 2n ways to do this since order matters.
• Second way to count: Add number of subsets of size k,
k = 0,1, ..., n to get the total number of ways.
• Setting these two ways of counting equal we have:
n n
n
2        ...   .
 0 1
n
n
• Note that the latter equality also follows from the binomial thm.
Do you see how? Also, the set of all subsets of a given set A is
called the power set of A.
Stirling's Formula
• To estimate n! for large values of n, we use
n!~ 2nπ  n n  e  n ,
n!
where ~ meansthatlim
 1.
n
n
n 
2nπ  n  e
• Example. By Stirling's formula,
2n  (n!) 2
nπ
~ n .
(2n)!
2