Report

CMPS 2433 Chapter 8 Counting Techniques Midwestern State University Dr. Ranette Halverson 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