# DARTMOUTH COSC 030 - 06binom (3 pages)

Previewing page 1 of 3 page document
View Full Document

## 06binom

Previewing page 1 of actual document.

View Full Document
View Full Document

## 06binom

54 views

Pages:
3
School:
Dartmouth College
Course:
Cosc 030 - Discrete Math Computer Sci
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 Unlocking...