DARTMOUTH COSC 030 - 06binom (3 pages)

Unformatted text preview:

Sum and Product Notation A more precise shorthand than n X CS 30 Discrete Mathematics i 1 n X Amit Chakrabarti 2j j 1 n Y i i 1 This product is denoted n pronounced n factorial j2 i 1 Permutations and Factorials Solution Assume WLOG that the list is 1 2 3 n Permutation a1 a2 an terms distinct each ai 1 2 n Generalized product principle number of choices is n n 1 n 2 1 1 n Y Binomial Coef2icients Problem How many permutations does a list of n distinct items have i 2 12 2 2 3 2 n 2 1 12 3 22 5 32 2n 1 n2 i 1 2 3 n Counting Subsets of Fixed Size Problem How many k element subsets does S have if S n Solution Let U A S A k We want U De2ine T a1 a2 ak Sk ai aj for i j De2ine MakeSet T U by MakeSet a1 a2 ak a1 a2 ak By our previous result this is a k to 1 correspondence Using the division and product principles U T k n n 1 n 2 n k n This result has a symbol k k 1 k Y n j 1 j 1 j pronounced n choose k Practice With n choose k Formula Alternate Formula and Symmetry n n n k n n n 1 0 n n 1 n n 1 n 2 2 n n 1 n 2 n 3 6 n n 1 n n 1 n 1 n n 1 n 2 1 n 3 1 n 4 1 n 5 n 6 1 3 4 5 6 6 10 15 20 n k k 1 1 n k n k Proof 1 Algebraic manipulation on whiteboard 1 4 10 k n n n n 1 Theorem For all 1 k n k k 1 k 1 3 n Pascal s Identity 1 2 Can you prove this identity another way Hint Bijection principle 1 n 1 k k 1 n n k n k n Values of for small n and k 0 1 2 n k 1 k 1 n k 1 Notice the symmetry between k and n k This shows Pascal s Triangle n 0 1 n Proof 2 Bijective proof hands in pockets tell a story 1 5 15 n n n 1 Pattern revealed k k 1 k 1 6 1 The town of Bijectiville has population n 1 The town hall serves free lunch to the 2irst k citizens to take a spot at its High Table When the Mayor is too busy to join clearly there are n choose k ways to 2ill the k spots If the Mayor joins leaving k 1 spots there are n choose k 1 ways to 2ill the table Either way the k spots are 2illed from the total population of n 1 so there are n 1 choose k ways to do