Great Theoretical Ideas In Computer Science Steven Rudich Lecture 11 CS 15 251 Feb 14 2004 Spring 2003 Carnegie Mellon University Counting III Pascal s Triangle Polynomials and Vector Programs X 1 X 2 X 3 n 1 X 1 1 2 3 n 1 n 1 X X X X X X 1 The Geometric Series 1 X1 X2 X 3 Xn 1 1 X The Infinite Geometric Series 1 X1 X2 X 3 Xn 1 1 X X 1 1 X1 X2 X 3 Xn X1 X 2 X 3 Xn Xn 1 1 X1 X2 X 3 Xn 1 Xn Xn 1 1 1 X1 X2 X 3 Xn 1 1 X 1 x 1 x 1 1 x x x x2 x2 1 1 aX1 a2X2 a3X 3 anXn 1 aX Geometric Series Linear Form 1 aX1 a2X2 anXn 1 bX1 b2X2 bnXn 1 1 aX 1 bX Geometric Series Quadratic Form 1 aX1 a2X2 anXn 1 bX1 b2X2 bnXn 1 c1X1 ck Xk Suppose we multiply this out to get a single infinite polynomial What is an expression for Cn 1 aX1 a2X2 anXn 1 bX1 b2X2 bnXn 1 c1X1 ck Xk cn a0bn a1bn 1 aibn i an 1b1 a nb0 1 aX1 a2X2 anXn 1 bX1 b2X2 bnXn 1 c1X1 ck Xk If a b then cn n 1 an a0bn a1bn 1 aibn i an 1b1 a nb0 an 1 a0bn a1bn 1 aibn i an 1b1 anb0 bn 1 a b a b a0bn a1bn 1 aibn i an 1b1 anb0 a1bn ai 1bn i a n b1 an 1b0 a0bn 1 a1bn ai 1bn i an 1b2 anb1 bn 1 an 1 bn 1 an 1 1 aX1 a2X2 anXn 1 bX1 b2X2 bnXn 1 c1X1 ck Xk if a b then cn an 1 bn 1 a b 0 n 1 n 1 i n i a b a b a b an 1b1 a nb0 1 aX1 a2X2 anXn 1 bX1 b2X2 bnXn 1 n 0 1 or n 0 1 1 aX 1 bX an 1 bn 1 a b Xn n 1 an Xn when a b Geometric Series Quadratic Form Previously we saw that Polynomials Count What is the coefcient of BA3N2 in the expansion of B A N 6 The number of ways to rearrange the letters in the word BANANA 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 Coefcients 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 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 We could discover new identities by substituting in different numbers for X One cool idea is to try complex roots of unity however the lecture is going in another direction 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 coefcients 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 coefcients 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 Pacal n n 1 Pascal n k Pascal n 1 k 1 Pascal n 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 2 2 1 2 0 1 2 1 3 3 3 …
View Full Document
Unlocking...