Transcript CMPS 2433 Chapter 8 Counting Techniques

CMPS 2433
Chapter 8
Counting Techniques
Midwestern State University
Review From Previous Chapters
• 2.6 Binary Search
• For an ordered list of 2n items, @most n+1 comparisons
are needed to find an item
• For an ordered list of n items, at most log2 n comparisons
are needed
• Example: How many comparisons for list of…
• 100o items?
• 1,000,000 items?
Review
• Permutation: an ordering of a set of elements
• Permutations of set S with n elements is n!
• Permutations of r elements taken from n is (n!)/(n-r)!
• Example - S contains 7 elements
• How many different permutations? 7!
• How many permutations of only 5 of the elements? 7!/3!
Review
Theorem 1.3: A set of N elements has exactly 2N subsets
• Consider S = {1, 3, 5, 7, 90} – include or not?
Theorem 2.10 (p. 89) :Set S has n elements. # of subsets
containing r elements is (n!)/(r! (n-r)!)
• Referred to as Combinations of n items taken r at a time.
C(n,r)
• Note: r! term eliminates duplicates
• Example: How many subsets of size 3 from S?
Section 8.2 ~ 3 Fundamental Principles
• Pigeonhole Principle: If pigeons are placed in pigeon holes
and there are more pigeons than holes, then some holes
must contain at least 2 pigeons. ~~ If number of pigeons is
more than k times the number of holes, then some hole
must contain at least k+1 pigeons.
Section 8.2 ~ 3 Fundamental Principles
• Applications: Pigeonhole Principle
• How many people must be selected from a collection of 15
couples to ensure at least one couple is selected?
• How many distinct integers must be chosen to assure there
are at least 10 having the same congruence modulo 7?
• Select any 5 points on the interior of an equilateral triangle
having sides length 1. Show that there is at least one pair of
points with distance between <= ½.
Fundamental Principle #2
• Multiplication Principle: Consider a procedure of k
steps. S’pose step 1 can be done in n1 ways, step 2 in n2
ways, etc. The number of different ways the entire
procedure can be performed is n1*n2*n3*…*nk.
Fundamental Principle #2
• Applications: Multiplication Principle
• Couple has 5 first names & 3 middle chosen for a baby.
How many different baby names?
• Binary numbers: How many different binary numbers of
length 8 are there? What are the values?
• Phone numbers: How many numbers are possible in the
940 area code? (First 2 digits cannot be 0 or 1)
• Example 8.10 (p. 410)
Fundamental Principle #3
• Addition Principle: Assume k sets with n1 elements in set
1, n2 in set 2, etc. and all elements are distinct. The
number of elements in the union of the sets is
n1+n2+n3+…+nk
• Note: Sometimes “solution” is to define the distinct sets
so that they can be easily counted.
Fundamental Principle #3
• Applications: Addition Principle
• Couple has 5 girl names and 7 boy names for baby. How
many different names?
• How many integers between 1 – 100 (inclusive) are even
or end in 5?
• Example 8.14 (p. 412)
Homework Section 8.2
• Section 8.2 – page 413+
• 1 – 36 ~ All except proofs
8.1 Pascal’s Triangle & Binomial Theorem
Theorem 8.1
• For integers r & n, 1 <= r <= n,
C(n,r) = C(n-1,r-1) + C(n-1,r)
• Example: C (7,5) = C (6,4) + C (6,5)
• Reminder: C(n,r) = n! / (r! (n-r)!)
Pascal’s Triangle
C(0,0)
C(1,0) C(1,1)
C(2,0) C(2,1) C(2,2)
C(3,0) C(3,1) C(3,2) C(3,3) etc…
Pascal’s Triangle
1
1
1
1
1
1
2
3
4
1
3
6
1
4
1 etc…
Application of Pascal’s Triangle
Theorem 8.2:
• If r and n are integers such that 0 <= r <= n, then
C(n,r) = C(n,n-r)
Example: C(5,2) = C(5,3)
Theorem 8.3: Binomial Theorem
For every positive integer n,
(x + y)n = C(n,0)xn + C(n,1)xn-1 y + … + C(n,n-1) x yn-1 + C(n,n)yn
C(n,r) are called binomial coefficients
Homework
• Section 8.1 – page 405+
• Problems 1 - 24