6.042/18.] Mathematics for Computer Science April 5, 2005 Srini devadas and Eric Lehman Lecture notes Counting Today we'll briefly review some facts you dervied in recitation on Friday and the to some applications of counting 1 The bookkeeper rule In recitation you learned that the number of ways to rearrange the letters in the word BOOKKEEPER is 1!2!2!3!1!1! Bs Os Ks E This is a special case of an exceptionally useful counting principle Rule 1 (Bookkeeper Rule). The number of sequences with ni copies of li, n2 copies of l2r and nk copies of lk is (m1+m2+….+mk)! provided l1,..., lk are distinct Let's review some applications and implications of the Bookkeeper Rule 1.1 20-Mile walks I'm planning a 20 miles walk, which should include 5 northward miles, 5 eastward miles, 5 southward miles, and 5 westward miles. How many different walks are possible? There is a bijection between such walks and sequences with 5NS,5Es, 5Ss, and 5 Ws. By the Bookkeeper Rule, the number of such 20!���� 6.042/18.062J Mathematics for Computer Science April 5, 2005 Srini Devadas and Eric Lehman Lecture Notes Counting III Today we’ll briefly review some facts you dervied in recitation on Friday and then turn to some applications of counting. 1 The Bookkeeper Rule In recitation you learned that the number of ways to rearrange the letters in the word BOOKKEEPER is: total letters 10! 1! 2! 2! 3! 1! 1! ���� ���� ���� ���� ���� ���� B’s O’s K’s E’s P’s R’s This is a special case of an exceptionally useful counting principle. Rule 1 (Bookkeeper Rule). The number of sequences with n1 copies of l1, n2 copies of l2, . . . , and nk copies of lk is (n1 + n2 + . . . + nk)! n1! n2! . . . nk! provided l1, . . . , lk are distinct. Let’s review some applications and implications of the Bookkeeper Rule. 1.1 20­Mile Walks I’m planning a 20 miles walk, which should include 5 northward miles, 5 eastward miles, 5 southward miles, and 5 westward miles. How many different walks are possible? There is a bijection between such walks and sequences with 5 N’s, 5 E’s, 5 S’s, and 5 W’s. By the Bookkeeper Rule, the number of such sequences is: 20! 5!4