DARTMOUTH COSC 030 - 06binom (3 pages)

Previewing page 1 of 3 page document View the full content.
View Full Document

06binom



Previewing page 1 of actual document.

View the full content.
View Full Document
View Full Document

06binom

54 views


Pages:
3
School:
Dartmouth College
Course:
Cosc 030 - Discrete Math Computer Sci
Discrete Math Computer Sci Documents
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 it Pascal s Identity Bijective Proof Let S be a set with S n 1 Let T A S A k Choose x S Put Tinc A T x A Texc A T x A disjoint U A S x A k 1 V A S x A k Observe The function f Tinc U given by f A A x is a bijection Also Texc V So n 1 k T Tinc Texc U V n k n 1 k Exercises More Bijective Proofs Give bijective proofs of these identities n n k n k n X n k 0 n X k 0 k 2n n 1 0 k k Binomial Theorem Concepts Sum and product notation n choose k notation 1 n Pascal s triangle Bijective proofs x y 2 x2 2xy y2 x y 3 x3 3x2y 3xy2 y3 6 x y x6 6x5y 15x4y2 20x3y3 15x2y4 6xy5 y6 Theorem x y n n X n k 0 k xn Theorems Symmetry of binom coef2icients Pascal s identity Binomial theorem k k y Proof outline bijective Consider formation of all x2y4 terms x y 6 x y x y x y x y x y x y Study Bee Skills Finding patterns in binom coeffs Practice with bijective proofs


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view 06binom and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 06binom and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?