Counting l kl k 2 Let A be all the permutations of the knights, and let b be the set of all possible seating arrangements at the round table. We can map each permutator in set A seating arrangement in set B by seating the first knight in the permutation anywhere, putting the second knight to his left, the third knight to the left of the second, and so forth all the way around the table. For example (k2,k4,k1,k3)→k3 This mapping is actually an n-to-1 function from A to B, since all n cyclic shifts of the original sequence map to the same seating arrangement. In the example, n=4 different sequences map to the same seating arranement (k2,k4,k1,k3) (k4,k1,k3,k2) (k1,k3,k2,k4) (ka,k2,k4,k1) Therefore, by the division rule, the number of circular seating arrangements is 1B=14 Note that A=n! since there are n! permutations of n knights 3 Inclusion-Exclusion How big is a union of sets? For example, suppose there are 60 Math majors, 200 EECS majors, and 40 Physics majors. How many students are there in these three departments?Counting II 7 ✧✦ ★✥ k1 k2 k3 k4 ✧✦ ★✥ k3 k4 k1 k2 Let A be all the permutations of the knights, and let B be the set of all possible seating arrangements at the round table. We can map each permutaton in set A to a circular seating arrangement in set B by seating the first knight in the permutation anywhere, putting the second knight to his left, the third knight to the left of the second, and so forth all the way around the table. For example: (k2, k4, k1, k3) ⇒ ✧✦ ★✥ k2 k4 k1 k3 This mapping is actually an n-to-1 function from A to B, since all n cyclic shifts of the original sequence map to the same seating arrangement. In the example, n = 4 different sequences map to the same seating arranement: (k2, k4, k1, k3) (k4, k1, k3, k2) (k1, k3, k2, k4) (k3, k2, k4, k1) ⇒ ✧✦ ★✥ k2 k4 k1 k3 Therefore, by the division rule, the number of circular seating arrangements is: |B| = |A| n = n! n = (n − 1)! Note that |A| = n! since there are n! permutations of n knights. 3 Inclusion-Exclusion How big is a union of sets? For example, suppose there are 60 Math majors, 200 EECS majors, and 40 Physics majors. How many students are there in these three departments?