Inclusion exclusion principle A A B B A B A B A B 1 Corollary If X Y then Y X Y X Y X Y X Y Y X Y X X X Y Y X Y X Proof For any sets X and Y we have Y Y X Y X as was shown in the Lemma But in case X Y Y X X So if X Y then Y Y X X where sets Y X and X are disjoint Y X X By the Rule of Sum Y Y X X or Y X Y X 2 Inclusion exclusion principle IEP for three sets Let s count the number of elements in the union of three sets A B C A B C associative law A B C A B C by IEP for A and B C A B C A B A C by distributive law A B C B C A B A C by IEP for B and C A B C B C A B A C A B A C by IEP for A B and A C A B C B C A B A C A B C 3 B A C A B C A B C B C A B A C A B C inclusion exclusion inclusion 4 Example Suppose A B and C represent three bus routes Let A B and C be also sets of stops for corresponding routes Suppose A has 25 stops B has 30 stops and C has 40 stops Suppose further that A and B share 6 stops A and C share 5 stops and B and C share 4 stops Suppose that A B and C share 2 stops a How many distinct stops are on the three bus routes B A A 25 B 30 C 40 A B 6 A C 5 B C 4 A B C 2 A B C C A B C A B C A B A C B C A B C 25 30 40 6 5 4 2 82 5 b How many stops for A are not stops for B Stops for A that are also stops for B are A elements of A B We can then represent A B as the union of two disjoint sets A B A A B A B C A A B A A B 25 6 19 c How many stops for A are not stops for both B and C We need to find A A B C B Since A B C A by the corollary we have A A B C 25 2 23 C 6 d How many stops for A are not stops for any other bus A B A A B C A B A C not disjoint A B C C A B 6 A C 5 A B A C A B C A A B C A B A C A B C A B C 2 A B C A A B A C A B C 16 25 6 5 2 7 Counting subsets Any subset X of the set A X A is a combination of size X from A elements So the number of subsets of cardinality X r of the set of cardinality A n is n n C n r binomial coefficients n r r r Example Let A 1 2 3 4 5 Find the number of 2 element subsets of A 5 5 4 C 5 2 10 3 2 2 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 8 a b 3 a b a b a b aaa aab aba abb baa bab bba bbb C 3 1 3 the number of ways to choose 1 b from 3 factors 1 2 3 C 3 2 3 the number of ways to choose 2 b s from 3 factors 2 3 1 3 1 2 a b 3 C 3 0 a3 b0 C 3 1 a2 b C 3 2 a b2 C 3 3 a0 b3 a3 3a2 b 3a b2 b3 9 Selection from Selection from Selection from First factor Second factor Third factor a b a b a b a a a a a b a b a a b b b a a b a b b b a b b b a3 a2b a2b ab2 a2b ab2 ab2 b3 1 2 3 3 2 2 3 1 1 3 1 2 1 2 3 10 In general for any n a b n C n 0 an b0 C n 1 an 1 b1 C n 2 an 2 b2 C n n 1 a1 bn 1 C n n a0 bn Using summation notation k n n k k C n k a b a b n Binomial theorem k 0 In particular 1 1 n 2n C n 0 C n 1 C n 2 C n n 1 C n n 11 The total number of subsets including empty set and set A itself is n empty set n n 1 2 1 C n 0 C n 1 C n 2 C n n 2 n 1 singletons 2 element the whole set subsets One more consequence of the Binomial Theorem 1 1 n 0 C n 0 C n 1 C n 2 C n 3 C n 0 C n 2 C n 4 C n 1 C n 3 C n 5 even cardinality odd cardinality 12 n A r 0 0 1 x x 2 x y x y x y 3 x y z x y z x y x z y z x y z w x y x z x w y z y w z w 4 x y z w 1 2 3 4 x y z x y z x y w x z w y z w x y z w 13 Binomial coefficients have the property C n 1 k C n k 1 C n k Number of k subsets of a set with n 1 elements include x 1 k n do not include x A n 1 Let x A be any element of A B A x A B x B n All k subsets of A either include x or not The number of k subsets that include x is the number of k 1 subsets of B Subsets of A that do not include x are k subsets of B 14 Pascal s Triangle 1 1 1 1 n 5 4 10 6 15 r 3 5 3 6 r 2 1 r 1 r 0 n 6 1 3 1 10 20 1 3 3 1 23 1 4 r 4 n 4 1 2 1 1 20 1 1 21 1 2 1 22 1 5 15 1 4 6 4 1 24 1 6 1 5 10 10 5 1 25 1 1 6 15 20 15 6 1 26 r 5 n 0 n 1 n …
View Full Document
Unlocking...