Discrete Mathematic教学课件（华南理工大学）Ch03-2 3-4 PigeonholePrincipleAndBinomialCoefficients2.pdfVIP

Discrete Mathematic Chapter 3: Counting 3.2 The Pigeonhole Principle 3.4 Binomial Coefficients Dr Patrick Chan School of Computer Science and Engineering South China University of Technology Agenda Ch 3.2 The Pigeonhole Principle Pigeonhole Principle Generalized Pigeonhole Principle Applications Ch 3.4 Binomial Coefficients Binomial Theorem Pascals Identity and Triangle Theorem related to Binomial Coefficients Chapter 3.2 3.4 2 Pigeonhole Principle Suppose that a flock of 26 pigeons flies into a set of 25 pigeonholes to roost What can we conclude? Chapter 3.2 3.4 3 Pigeonhole Principle A least one of these 25 pigeonholes must have at least two pigeons in it Because there are 26 pigeons but only 25 pigeonholes This is Pigeonhole Principle Chapter 3.2 3.4 4 Pigeonhole Principle Pigeonhole Principle If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more of the objects Also called the Dirichlet Drawer Principle the nineteenthcentury German mathematician Dirichlet Proof by contraposition (p →→ q ≡¬≡ ¬q →→ ¬¬p) →→ ≡≡ ¬¬ →→ ¬¬ Suppose that none of the k boxes contains more than one object Then the total number of objects would be at most k This is a contradiction Chapter 3.2 3.4 5 Pigeonhole Principle Corollary A function f from a set with k + 1 or more elements to a set with k elements is not one toone