15-251Great Theoretical Ideas in Computer Science X1 X2 + + X3Lecture 8, September 18, 2008Counting IIIReview from last time...Arrange n symbols: r1 of type 1, r2 of type 2, …, rk of type knr1n-r1r2…n - r1 - r2 - … - rk-1rk(n-r1)!(n-r1-r2)!r2!n!(n-r1)!r1!=…=n!r1!r2! … rk!14!2!3!2!= 3,632,428,800CARNEGIEMELLON5 distinct pirates want to divide 20 identical, indivisible bars of gold. How many different ways can they divide up the loot?Sequences with 20 G’s and 4 /’sHow many different ways to divide up the loot?244How many different ways can n distinct pirates divide k identical, indivisible bars of gold?n + k - 1n - 1n + k - 1k=How many integer solutions to the following equations?x1 + x2 + x3 + … + xn = kx1, x2, x3, …, xn ! 0n + k - 1n - 1n + k - 1k=Identical/Distinct DiceSuppose that we roll seven diceHow many different outcomes are there, if order matters?67What if order doesn’t matter?(E.g., Yahtzee)127(Corresponds to 6 pirates and 7 bars of gold)Identical/Distinct ObjectsIf we are putting k objects into n distinct bins.Objects are distinguishablenkObjects are indistinguishablek+n-1kbinomial expressionBinomial CoefficientsThe Binomial Formulan1(1+X)n =n0X0+ X1+…+nnXnWhat is the coefficient of (X1r1X2r2…Xkrk)in the expansion of(X1+X2+X3+…+Xk)n?n!r1!r2!...rk!And now for some more counting...Power Series Representation(1+X)n =nkXk!k = 0nnkXk!k = 0"=“Product form” or“Generating form”“Power Series” or “Taylor Series” ExpansionFor k>n,nk= 0By playing these two representations against each other we obtain a new representation of a previous insight:(1+X)n =nkXk!k = 0nLet x = 1,nk!k = 0n2n =The number of subsets of an n-element setBy varying x, we can discover new identities:(1+X)n =nkXk!k = 0nLet x = -1,nk!k = 0n0 =(-1)kEquivalently,nk!k evennnk!k oddn=The number of subsets with even size is the same as the number of subsets with odd sizeProofs that work by manipulating algebraic forms are called “algebraic” arguments. Proofs that build a bijection are called “combinatorial” arguments(1+X)n =nkXk!k = 0nLet 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 just saw an algebraic proof that |On | = | En |nk!k evennnk!k oddn=A Combinatorial ProofLet On be the set of binary strings of length n with an odd number of onesLet En be the set of binary strings of length n with an even number of onesA combinatorial proof must construct a bijection between On and En An Attempt at a BijectionLet fn be the function that takes an n-bit string and flips all its bitsfn is clearly a one-to-one and onto function...but do even n work? In f6 we havefor odd n. E.g. in f7 we have:110011 ! 001100101010 ! 0101010010011 ! 11011001001101 ! 0110010Uh oh. Complementing maps evens to evens!A Correspondence That Works for all nLet fn be the function that takes an n-bit string and flips only the first bit. For example,0010011 ! 10100111001101 ! 0001101110011 ! 010011101010 ! 001010The binomial coefficients have so many representations that many fundamental mathematical identities emerge…(1+X)n =nkXk!k = 0nnkn-1kn-1k-1+=Set of allk-subsetsof {1..n}Either wedo not pick n:then we have topick k elementsout of the remaining n-1.Or wedo pick n:then we have topick k-1 elts.out of the remaining n-1.The Binomial Formula(1+X)0 =(1+X)1 =(1+X)2 =(1+X)3 =(1+X)4 =11 + 1X1 + 2X + 1X21 + 3X + 3X2 + 1X31 + 4X + 6X2 + 4X3 + 1X4Pascal’s Triangle: kth row are coefficients of (1+X)kInductive definition of kth entry of nth row:Pascal(n,0) = Pascal (n,n) = 1; Pascal(n,k) = Pascal(n-1,k-1) + Pascal(n-1,k)“Pascal’s Triangle”00= 110= 111= 120= 121= 222= 1• Al-Karaji, Baghdad 953-1029• Chu Shin-Chieh 1303• Blaise Pascal 165430= 131= 332= 333= 1Pascal’s Triangle“It is extraordinaryhow fertile inproperties thetriangle is.Everyone cantry hishand”11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 111 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1Summing the Rows++ ++ + ++ + + ++ + + + ++ + + + + +nk!k = 0n2n == 1= 2= 4= 8= 16= 32= 6411 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 11 + 15 + 15 + 1 6 + 20 + 6=Odds and Evens11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1Summing on 1st Avenue!i = 1ni1=!i = 1nin+12=Summing on kth Avenue!i = knikn+1k+1=11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1Fibonacci Numbers= 2= 3= 5= 8= 1311 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 111 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1Sums of Squares2 2 22 2 2 211 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1Al-Karaji Squares+2#+2#+2#+2#+2#= 1= 4= 9= 16= 25= 36Pascal Mod 2All these properties can be proved inductively and algebraically. We will give combinatorial proofs using the Manhattan block walking representation of binomial coefficientsHow many shortest routes from A to B?BA105Manhattanjth street kth avenue1024301234There are shortest routes from (0,0) to (j,k)j+kkManhattanLevel n kth avenue1024301234There are shortest routes from (0,0) to (n-k,k)nkManhattanLevel n kth avenue1024301234There areshortest routes from (0,0) tonklevel n and kth avenueLevel n kth avenue10243012341111111112334461155101066151520Level n kth avenue102431111111112334461155101066151520nkn-1k-1n-1k=++Level n kth avenue10243012342nnnk!k = 0n2=Level n kth avenue1024301234n+1k+1ik!i = kn=Handout on generating functions• Polynomials count• Binomial formula• Combinatorial proofs
View Full Document
Unlocking...