PowerPoint PresentationSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 211Inclusion-exclusion principle A BAB|AB|= | A | + |B| | AB|2Corollary. If X Y, then |Y X | = |Y||X|X Y /|Y X | |Y||X|XY XY |Y X | = |Y||X|X Y Proof. For any sets X and Y we have Y = (Y X)(YX) (as was shown in the Lemma). But, in case X Y, YX=X. So, if X Y, then Y = (Y X)X, where sets (Y X) and Xare disjoint, (Y X) X=. By the Rule of Sum:|Y|=| Y X | +|X|, or |Y X | = |Y||X |.3Inclusion-exclusion principle (IEP) for three sets.Let’s count the number of elements in the union of three sets,| ABC|= | A| +|BC| | A (BC)|…………by IEP for A and BC= | A| +|BC | | (AB)(AC)|……by distributive law = | A| +|B| +|C| |BC| (|AB| + |AC| | (AB)(AC)|) by IEP for AB and AC = | A| +|B| +|C| |BC| |AB| |AC| + | ABC| = | A(BC)|…………….associative law= | A| +|B| +|C| |BC| |(AB)(AC)|….by IEP for B and C4 A B C | ABC|= | A| +|B| + |C|inclusion |BC| |AB| |AC|exclusion+ | ABC| inclusion5Example. 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?|A|=25, |B|=30, |C|= 40 |AB|=6, |AC|=5, |BC|=4| ABC | = 2 | ABC|=|A|+ |B|+ |C| |AB| |AC| |BC| + | ABC | = = 25+30+40 6 5 4+2=82ABC A B C6b) How many stops for A are not stops for B? A= (AB)(AB)| AB| = |A| |AB| =25 6=19c) How many stops for A are not stops for both B and C?AB AB C C BA|A| | ABC |=25 2=23 Stops for A that are also stops for B are elements of AB. We can then represent A as the union of two disjoint sets: We need to find |A ABC|. Since ABC A, by the corollary we have:7|AB|=6, |AC|=5| ABC | = 2 |A BC| = |A| |AB| | AC| + | ABC | =1625 6 5 2|A| = |A BC|+| AB|+| AC| | ABC | d) How many stops for A are not stops for any other bus?ABC (A B) C A= (ABC)(AB)(AC) not disjoint(AB)(AC) = ABC 8Counting 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 setof cardinality |A|=n is rnrrnnrnC!)!(!),(binomial coefficientsExample. Let A = {1, 2, 3, 4, 5}. Find the number of 2-element subsets of A. 102452!3!5!(5,2) C{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5},{4, 5}9(a + b)3= (a + b) (a + b) (a + b) = aaa + aab + aba + abb + baa + bab + bba + bbb C (3, 1)=3the number of ways to choose 1 b from 3 factors:{1}, {2}, {3}C (3, 2)=3the 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)a2b + C (3, 2)a b2 + C (3, 3)a0b3 = a3 + 3a2b + 3a b2 + b310Selection fromFirst factor (a + b) a a a a b b b b Selection fromSecond factor (a + b) a a b b a a b b Selection fromThird factor (a + b) a b a b a b a b a3a2ba2bab2 a2bab2ab2b3{1, 2, 3} {3} {2} {2, 3} {1} {1, 3} {1, 2} {1, 2, 3}11In 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: (a + b)n= nkkkk-nbak n,C0 )(Binomial theorem In particular, (1+1)n = 2n =C (n, 0) + C (n, 1) + C (n, 2) + … + C (n, n-1) + C (n, n)12The total number of subsets (including empty set and set Aitself) isnnnCnCnCnC 2),(...2) ,(1) ,(0) ,( One more consequence of the Binomial Theorem:(11)n = 0 =C (n, 0) C (n, 1) + C (n, 2) C (n, 3)+ … 1=n=n(n 1)/2 ==1empty set singletons 2-element subsetsthe whole setC (n, 0) + C (n, 2) + C (n, 4)+ …=C (n, 1) + C (n, 3) + C (n, 5)+ … even cardinality odd cardinality133 {x, y, z} {x} {x, y} {x, y, z} {y} {x, z} {z} {y, z}n A r=0 1 2 3 4 0 1 {x} {x}2 {x, y} {x} {x, y} {y} 4 {x, y, z, w} {x} {x, y} {x, y, z} {x, y, z, w} {y} {x, z} {x, y, w} {z} {x,w} {x, z, w} {w} {y, z} {y, z, w} {y,w} {z,w}14Binomial coefficients have the propertyC (n+1, k) = C (n, k1) + C (n, k) ( 1 k n )| A |= n+1 B = A { x }, A= B {x}, |B|=n Let x A be any element of A All k subsets of A either include x, or not. Number of k-subsets of a set with n+1 elementsinclude x do not include xThe number of k subsets that include x is the number of k1 subsets of B. Subsets of A that do not include x, are k subsets of B.15Pascal’s Trianglen=3n=0n=1n=2n=4n=5n=6r=0r=1r=2r=3r=4r=511 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 11=20 1+1=211+2+1=221+3+3+1=231+4+6+4+1=241+5+10+10+5+1=251+6+15+20+15+6+1=2616Lets count separately subsets with odd and even cardinalities11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1r=0r=1r=2r=3r=4r=5The sums of cardinalities for odd and even subsets in each row are equal!n=3n=0n=1n=2n=4n=5n=61+1=21+6+1=4+41+10+5=5+10+11+15+15+1=6+20+61+3=3+1evenodd1=117Example Let A = {a, b, c, d }.a) Find the number of subsets of even cardinality.We have n=|A|=4. The number of even subsets is 24/2=8, i.e. one half of the total number of subsets. C(4, 2)=6Here they are:, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c, d }.C(4, 0)=1C(4, 4)=118b) The number
View Full Document
Unlocking...