Counting II: Pascal, Binomials, and Other TricksGreat Theoretical Ideas In Computer ScienceV. AdamchikD. SleatorCS 15-251 Spring 2010Lecture 5 Jan. 26, 2010 Carnegie Mellon University++()+() = ?Permutations vs. Combinationsn!(n-r)!n!r!(n-r)!=nrOrderedUnorderedSubsets of r out of n distinct objectsHow many ways to rearrange the letters in the word “SYSTEMS”?SYSTEMS7 places to put the Y, 6 places to put the T, 5 places to put the E, 4 places to put the M, and the S’s are forced7 X 6 X 5 X 4 = 840_,_,_,_,_,_,_SYSTEMSLet’s pretend that the S’s are distinct:S1YS2TEMS3There are 7! permutations of S1YS2TEMS3But when we stop pretending we see that we have counted each arrangement of SYSTEMS 3! times, once for each of 3! rearrangements of S1S2S37!3!= 840Arrange n symbols: r1of type 1, r2of type 2, …, rkof type knr1n-r1r2…n - r1 - r2- … - rk-1rkn!(n-r1)!r1!(n-r1)!(n-r1-r2)!r2!=…=n!r1!r2! … rk!How many ways to rearrange the letters in the word “CARNEGIEMELLON”?14!2!3!2!= 3,632,428,800Multinomial Coefficients!!...rr!rn!nr...rr if 0,r;...;r;rnk21k21k21Four ways of choosingWe will choose 2-letters word from the alphabet (L,U,C,K,Y}1) C(5,2) no repetitions, the order is NOT importantLU = ULFour ways of choosingWe will choose 2-letters word from the alphabet (L,U,C,K,Y}2) P(5,2) no repetitions, the order is importantLU != ULP(n,r)=n*(n-1)*…*(n-r+1)Four ways of choosingWe will choose 2-letters word from the alphabet (L,U,C,K,Y}3) 52=25 with repetitions, the order is importantFour ways of choosingWe will choose 2-letter words from the alphabet {L,U,C,K,Y}4) ???? repetitions, the order is NOT importantC(5,2) + {LL,UU,CC,KK,YY} = 155 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 /’sSequences with 20 G’s and 4 /’s1st pirate gets 22ndpirate gets 13rdand 5thget nothing4thgets 17GG/G//GGGGGGGGGGGGGGGGG/represents the following division among the piratesSequences with 20 G’s and 4 /’sGG/G//GGGGGGGGGGGGGGGGG/In general, the kthpirate gets the number of G’s after the k-1st/ and before the kth/. This gives a correspondence between divisions of the gold and sequences with 20 G’s and 4 /’s.How many different ways to divide up the loot?1-51-520424How many sequences with 20 G’s and 4 /’s?How many different ways can n distinct pirates divide k identical, indivisible bars of gold?k1kn1-n1-knHow many different ways to put kindistinguishable balls into ndistinguishable urns.k1kn1-n1-knAnother interpretationHow many integer solutions to the following equations?0x,x,x,x,x20xxxxx5432154321Another interpretationThink of xkas being the number of gold bars that are allottedto pirate k.24 4How many integer nonnegativesolutions to the following equations?0x,...,x,xkxxxn21n21...k1kn1-n1-knHow many integer positive solutions to the following equations?x1+ x2+ x3+ … + xn= kx1, x2, x3, …, xn> 0bijection with solutions toy1+ y2+ y3+ … + yn= k-ny1, y2, y3, …, yn≥ 0Think of xk-> yk+1Remember to distinguish betweenIdentical / Distinct ObjectsIf we are putting k objects into n distinct bins.k objects are distinguishablek objects are indistinguishablen+k-1knkPigeonhole PrincipleIf there are more pigeons than pigeonholes, then some pigeonholes must contain two or more pigeonsPigeonhole PrincipleIf there are more pigeons than pigeonholes, then some pigeonholes must contain two or more pigeonsExample:two people in Pittsburgh must have the same number of hairs on their headsPigeonhole PrincipleProblem:among any n integer numbers, there are some whose sum is divisible by n.Among any n integer numbers, there are some whose sum is divisible by n.Exist si= sk(mod n). Take si- skConsider si=x1 +…+ximodulo n. How many si? Remainders are {0, 1, 2, …, n-1}.Pigeonhole PrincipleProblem:The numbers 1 to 10 are arranged in random order around a circle. Show that there are three consecutive numbers whose sum is at least 17.What are pigeons? And what are pigeonholes?The numbers 1 to 10 are arranged in random order around a circle. Show that there are three consecutive numbers whose sum is at least 17Pigeons: S1+ .. + S10= 3 (a1+a2+a10) = 3*55 = 165Let S1=a1+a2+a3, … S10=a10+a1+a2There are 10 pigeonholes.Since 165 > 10 *16, at least one pigeon-hole hasat least 16 + 1 pigeonsPigeonhole PrincipleProblem:Show that for some integer k > 1, 3kends with 0001 (in its decimal representation).What are pigeons? And what are pigeonholes?Show that for some integer k > 1, 3kends with 0001 3k= 3m mod (10000), m < kChoose 10001 numbers: 31,32,…, 3100013k-m= q*10000 + 1 ends with 00013k-m= 1 mod (10000)Now, something completely different…knkn0knyx kny)(xPOLYNOMIALS EXPRESSCHOICES AND OUTCOMESProducts of Sum = Sums of Products++()+() =+++++b2b3b1t1t2t1t2t1t2b2b3b1t1t2t1t2t1t2b1t1b1t2b2t2b2t1b3t1b3t2(b1+ b2+ b3)(t1+ t2) = b1t1+ b1t2+ b2t1+ b2t2+ b3t1+ b3t2There is a correspondence between paths in a choice tree and the cross terms of the product of polynomials!1 X 1 X1 X 1 X1 X1 X1 XChoice tree for terms of (1+X)31XXX2XX2X2X3Combine like terms to get 1 + 3X + 3X2+ X31 X 1 X1 X 1 X1 X1 X1 X(1+X)3= 1 + 3X + 3X2+ X31XXX2XX2X2X3What is the combinatorial meaning of those coefficients?In how many ways canwe create a x2term?What is a closed form expression for ck?nn2210nxc...xcxccx)(1In how many ways can we create a x2term?What is a closed form expression for cn?n timesck, the coefficient of Xk, is the number of paths with exactlyk X’s. (1 X)nX X X X X( )( )( )( )...( )1 1 1 1 1After multiplying things out, but before combining like terms, we get 2ncross terms, each corresponding to a path in the choice tree. knckThe Binomial Theorembinomial expressionBinomial Coefficientsn2nxnn...x2nx1n0nx)(1The Binomial Formulaknkn0knyxkny)(xWhat is the coefficient of EMPTY in the expansion of(E + M + P + T + Y)5 ?5!What is the coefficient of EMP3TY in the expansion of(E + M + P + T + Y)7 ?The number of ways to rearrange the letters in the word SYSTEMSWhat is the coefficient of BA3N2in the expansion of(B + A + N)6?The number of ways to rearrange the letters in the word BANANAWhat is the coefficient of in the expansion of(X1+X2+…+Xk)n?nr r r rk!! ! !... !1 2 3X X X Xr r rkrk1 2 31 2 3...Multinomial Coefficients!!...rr!rn!nr...rr if 0,r;...;r;rnk21k21k21The Multinomial Formulaik,,r=n3k1221kn21rrrr321kr r ...,r21kX +X +...+ Xn= X X X ...Xr ;r ;...;rOn to Pascal…The binomial coefficients have so
View Full Document
Unlocking...