Great Theoretical Ideas In Computer Science John Lafferty Lecture 8 CS 15 251 Sept 21 2006 Fall 2006 Carnegie Mellon University Counting III Pascal s Triangle Polynomials and Vector Programs X 1 X 2 X 3 Last time we saw that Polynomials Count Choice tree for terms of 1 X 3 1 1 1 1 X X X X 1 1 X X X 1 X 1 X X2 X X2 X2 X3 Combine like terms to get 1 3X 3X2 X3 The Binomial Formula 1 X n nI F nI nI nI nI F F F F GJ G X G X G X G X J J J J 0K H 1K H 2K kK nK H H H 2 k Binomial Coefficients binomial expression n The Binomial Formula n k n 1 x x k 0 k n One polynomial two representations n k n 1 x x k 0 k n Product form or Generating form Additive form or Expanded form What is the coefficient of BA3N2 in the expansion of B A N 6 The number of ways to rearrange the letters in the word BANANA Multinomial Coefficients R 0 if r r r F n I S G J r r r H K n Tr r r 1 1 2 2 k 1 2 F n I FnI G J G J k n kK H kK H k k n The Multinomial Formula X1 X2 X n k r r r n rk 3 1 2 X X X X 1 2 3 k r r r r1 r2 rk 1 2 k ri n Power Series Representation n k 1 x x k k 0 n n n k x k k 0 Closed form or Generating form n Since 0 if k n k Power series Taylor series expansion By playing these two representations against each other we obtain a new representation of a previous insight n k 1 x x k 0 k n n Let x 1 n 2 k 0 k 123 n n The number of subsets of an n element set By varying x we can discover new identities n n k n 1 x x k 0 k Let x 1 n 0 1 k k 0 k n Equivalently n n n n 1 2 k k k even k odd n The number of even sized subsets of an n element set is the same as the number of oddsized subsets n k 1 x x k 0 k n n Let x 1 n k 0 1 k 0 k n Equivalently n n n n 1 k k 2 k even k odd n n k 1 x x k k 0 n n Proofs that work by manipulating algebraic forms are called algebraic arguments Proofs that build a 1 1 onto correspondence are called combinatorial arguments n n n n 1 2 k k odd k k even n Let On be the set of binary strings of length n with an odd number of ones Let En be the set of binary strings of length n with an even number of ones We gave an algebraic proof that On En A Combinatorial Proof Let On be the set of binary strings of length n with an odd number of ones Let En be the set of binary strings of length n with an even number of ones A combinatorial proof must construct a oneto one correspondence between On and En An attempt at a correspondence Let fn be the function that takes an n bit string and flips all its bits fn is clearly a one to one and onto function but do even n work In f6 we have for odd n E g in f7 we have 110011 001100 101010 010101 0010011 1101100 1001101 0110010 Uh oh Complementing maps evens to evens A correspondence that works for all n Let fn be the function that takes an n bit string and flips only the first bit For example 0010011 1010011 1001101 0001101 110011 010011 101010 001010 n k 1 x x k k 0 n n The binomial coefficients have so many representations that many fundamental mathematical identities emerge The Binomial Formula 1 X 0 1 1 X 1 1 1X 1 X 2 1 2X 1X2 1 X 3 1 3X 3X2 1X3 1 X 4 1 4X 6X2 4X3 1X4 Pascal s Triangle kth row are the coefficients of 1 X k 1 X 0 1 1 X 1 1 1X 1 X 2 1 2X 1X2 1 X 3 1 3X 3X2 1X3 1 X 4 1 4X 6X2 4X3 1X4 kth Row Of Pascal s Triangle n n n n n 0 1 2 k n 1 X 0 1 1 X 1 1 1X 1 X 2 1 2X 1X2 1 X 3 1 3X 3X2 1X3 1 X 4 1 4X 6X2 4X3 1X4 Inductive definition of kth entry of nth row Pascal n 0 Pascal n n 1 Pascal n k Pascal n 1 k 1 Pascal n1 k 1 X 0 1 1 X 1 1 1X 1 X 2 1 2X 1X2 1 X 3 1 3X 3X2 1X3 1 X 4 1 4X 6X2 4X3 1X4 Pascal s Triangle 0 0 1 1 1 0 1 1 1 2 0 1 3 0 1 2 2 2 1 2 1 3 3 3 3 3 1 2 3 1 Al Karaji Baghdad 953 1029 Chu Shin Chieh 1303 The Precious Mirror of the Four Elements Known in Europe by 1529 Blaise Pascal 1654 Pascal s Triangle 1 1 1 1 It is extraordinary how fertile in 1 1 properties the triangle is 1 2 1 Everyone can try his 1 3 3 1 hand 4 5 6 6 10 15 4 10 20 1 5 15 1 6 1 Summing The Rows 1 1 1 1 2 1 2 1 4 1 3 3 1 8 1 4 6 4 1 16 1 5 10 10 5 1 32 n n 2 k 0 k n 1 6 15 20 15 6 1 64 1 1 1 1 1 1 1 2 3 4 5 6 1 3 6 10 15 1 1 4 10 20 1 5 15 6 20 6 1 15 15 1 1 6 1 Summing on 1st Avenue 1 1 1 1 1 1 1 6 2 3 4 5 1 3 6 10 15 1 1 4 1 10 5 20 i n 1 n n 1 i 1 2 2 i k i k n 15 n 1 6 1 Summing on kth Avenue 1 1 1 1 1 1 1 6 2 3 4 5 1 3 6 10 15 1 1 4 1 10 5 20 i n 1 k k 1 i k n 15 1 6 1 1 1 1 2 3 1 2 1 5 8 1 3 3 1 13 1 1 6 1 4 5 10 15 6 4 10 20 1 5 15 1 6 1 1 1 1 12 22 …
View Full Document
Unlocking...