Great Theoretical Ideas In Computer Science V Adamchik D Sleator Lecture 5 CS 15 251 Jan 26 2010 Spring 2010 Carnegie Mellon University Counting II Pascal Binomials and Other Tricks Permutations vs Combinations Subsets of r out of n distinct objects n n r n n r n r r Ordered Unordered How many ways to rearrange the letters in the word SYSTEMS SYSTEMS 7 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 forced 7 X 6 X 5 X 4 840 SYSTEMS Let s pretend that the S s are distinct S1YS2TEMS3 There are 7 permutations of S1YS2TEMS3 But when we stop pretending we see that we have counted each arrangement of SYSTEMS 3 times once for each of 3 rearrangements of S1S2S3 7 3 840 Arrange n symbols r1 of type 1 r2 of type 2 rk of type k n r1 n r1 r2 n r1 r2 rk 1 rk n n r1 n r1 r1 n r1 r2 r2 n r1 r2 rk How many ways to rearrange the letters in the word CARNEGIEMELLON 14 3 632 428 800 2 3 2 Multinomial Coefficients n r1 r2 rk 0 if r1 r2 rk n r1 r2 rk n Four ways of choosing We will choose 2 letters word from the alphabet L U C K Y 1 C 5 2 no repetitions the order is NOT important LU UL Four ways of choosing We will choose 2 letters word from the alphabet L U C K Y 2 P 5 2 no repetitions the order is important LU UL P n r n n 1 n r 1 Four ways of choosing We will choose 2 letters word from the alphabet L U C K Y 3 52 25 with repetitions the order is important Four ways of choosing We will choose 2 letter words from the alphabet L U C K Y 4 repetitions the order is NOT important C 5 2 LL UU CC KK YY 15 5 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 s Sequences with 20 G s and 4 s GG G GGGGGGGGGGGGGGGGG represents the following division among the pirates 1st pirate gets 2 2nd pirate gets 1 3rd and 5th get nothing 4th gets 17 Sequences with 20 G s and 4 s GG G GGGGGGGGGGGGGGGGG In general the kth pirate 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 How many sequences with 20 G s and 4 s 24 4 20 5 1 5 1 How many different ways can n distinct pirates divide k identical indivisible bars of gold n k 1 n 1 n k 1 k Another interpretation How many different ways to put k indistinguishable balls into n distinguishable urns n k 1 n 1 n k 1 k Another interpretation How many integer solutions to the following equations x1 x2 x3 x4 x5 x1 x2 x3 x4 x5 0 Think of xk as being the number of gold bars that are allotted to pirate k 20 24 4 How many integer nonnegative solutions to the following equations x1 x2 xn x1 x2 xn n k 1 n 1 k 0 n k 1 k How many integer positive solutions to the following equations x1 x2 x3 xn k x1 x2 x3 xn 0 Think of xk yk 1 bijection with solutions to y1 y2 y3 yn k n y1 y2 y3 yn 0 Remember to distinguish between Identical Distinct Objects If we are putting k objects into n distinct bins k objects are distinguishable k objects are indistinguishable nk n k 1 k Pigeonhole Principle If there are more pigeons than pigeonholes then some pigeonholes must contain two or more pigeons Pigeonhole Principle If there are more pigeons than pigeonholes then some pigeonholes must contain two or more pigeons Example two people in Pittsburgh must have the same number of hairs on their heads Pigeonhole Principle Problem 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 Consider si x1 xi modulo n How many si Remainders are 0 1 2 n 1 Exist si sk mod n Take si sk Pigeonhole Principle Problem 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 17 Let S1 a1 a2 a3 S10 a10 a1 a2 There are 10 pigeonholes Pigeons S1 S10 3 a1 a2 a10 3 55 165 Since 165 10 16 at least one pigeon hole has at least 16 1 pigeons Pigeonhole Principle Problem Show that for some integer k 1 3k ends with 0001 in its decimal representation What are pigeons And what are pigeonholes Show that for some integer k 1 3k ends with 0001 Choose 10001 numbers 31 32 310001 3k 3m mod 10000 m k 3k m 1 mod 10000 3k m q 10000 1 ends with 0001 Now something completely different x y n n k 0 n k n x y k k POLYNOMIALS EXPRESS CHOICES AND OUTCOMES Products of Sum Sums of Products b1 t1 t2 b3 b2 t1 t2 t1 t2 t1 b1 b2 t2 t1 b1 t1 b1 t2 b3 t2 t1 t2 b2 t1 b2 t2 b3 t1 b3 t2 b1 b2 b3 t1 t2 b1t1 b1t2 b2t1 b2t2 b3t1 b3t2 There is a correspondence between paths in a choice tree and the cross terms of the product of polynomials 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 1 X 3 1 3X 3X2 X3 In how many ways can we create a x2 term 1 1 1 1 X X X X 1 1 X X X 1 X 1 X X2 X X2 X2 X3 What is the combinatorial meaning of those coefficients What is a closed form expression for ck 1 x n c0 c1x c2x 2 cn x n In how many ways can we create a x2 term What is a closed form expression for cn 1 X 1 n X 1 n times X 1 X 1 X 1 X After multiplying things out but before combining like terms we get 2n cross terms each corresponding to a path in the choice tree ck the coefficient of Xk is the number of paths with …
View Full Document
Unlocking...