4.5.2 Applications of Inclusion-Exclusion principle The number of r-combinations of multiset s 1. The number of r-combinations of multiset s If r<n, and there is in general, no simple formula for the number of r-combinations of S. Nonetheless a solution can be obtained b the inclusion-exclusion principle 4.5
▪ 4.5.2 Applications of Inclusion-Exclusion principle ▪ The number of r-combinations of multiset S ▪ 1. The number of r-combinations of multiset S ▪ If r<n, and there is, in general, no simple formula for the number of r-combinations of S. Nonetheless a solution can be obtained by the inclusion-exclusion principle 4.5
Example: Determine the number of 10-combinations of multiset s={3·a,4·b,5c} Solution: We shall apply the inclusion-exclusion principle to the set y of all 10-combinations of the multiset D=(oo.a b,o·c} Let p, be the property that a 10-combination of D has more than 3 as Let P2 be the property that a 10-combination of D has mote than 4 b's Let p3 be the property that a 10 combination of d has mote than 5c's Fori=1, 2, 3 let a i be the set consisting of those 10 combinations of d which have property P The number of 10-combinations of s is then the number of 10-combinations of D which have none of the properties p1, P. and p ∩A2∩
▪ Example: Determine the number of 10-combinations of multiset S={3·a,4·b,5·c}. ▪ Solution：We shall apply the inclusion-exclusion principle to the set Y of all 10-combinations of the multiset D={·a, ·b, ·c}. ▪ Let P1 be the property that a 10-combination of D has more than 3 a’s. Let P2 be the property that a 10-combination of D has mote than 4 b’s. Let P3 be the property that a 10- combination of D has mote than 5 c’s. ▪ For i=1,2,3 let Ai be the set consisting of those 10- combinations of D which have property Pi . ▪ The number of 10-combinations of S is then the number of 10-combinations of D which have none of the properties P1 , P2 , and P3 . A1 A2 A3
The set a consists of all 10-combinations of d in which a occurs at least 4 time If we take any one of these 10-combinations in a and remove 4 a's. we are left with a 6 combination of d Conversely, if we take a 6-combination of D and add 4 as to it, we get a 10-combination of D in which a occurs at least 4 times Thus the number of 10-combinations in A1 equals the number of 6-combinations of D Hence,|A=C(3+6-1,6)=((8,6=C(8,2)
▪ The set A1 consists of all 10-combinations of D in which a occurs at least 4 time. ▪ If we take any one of these 10-combinations in A1 and remove 4 a’s, we are left with a 6- combination of D. ▪ Conversely, if we take a 6-combination of D and add 4 a’s to it, we get a 10-combination of D in which a occurs at least 4 times. ▪ Thus the number of 10-combinations in A1 equals the number of 6-combinations of D. Hence, |A1 |=C(3+6-1,6)=C(8,6)=C(8,2)
Example: What is the number of integeal solutions of the equation 1+x2+x3=5 which satisfy0≤x1s2,0≤x2S2,l≤x3≤5? Solution: We introduce new variables X=X-1 3 and our equation becomes X+x2+x3=4 The inequalities on the xi and x3 are satisfied if and only if 0≤x1≤2,0≤x2≤2,0≤x3≤4. 4- combinations of multiset{2·a,2b,4·e}
▪ Example: What is the number of integeal solutions of the equation ▪ x1+x2+x3=5 ▪ which satisfy 0x12,0x22,1x35? ▪ Solution: We introduce new variables, ▪ x3 '=x3 -1 ▪ and our equation becomes x1+x2+x3 '=4. ▪ The inequalities on the xi and x3' are satisfied if and only if ▪ 0x12,0x22, 0x3 '4. ▪ 4-combinations of multiset {2·a,2·b,4·c}
2. Derangements A derangement of (1, 2,..., n is a permutation ii2.in of (1, 2,.., n in which no integer is in its natural position i11,2≠2,…n≠n We denote by d the number of derangements of{1,2,…,n} Theorem4.l5:Forn≥1, D=n!(1 ∴ l!2!13
▪ 2.Derangements ▪ A derangement of {1,2,…,n} is a permutation i1 i2…in of {1,2,…,n} in which no integer is in its natural position: ▪ i11,i22,…,inn. ▪ We denote by Dn the number of derangements of {1,2,…,n}. ▪ Theorem 4.15：For n1, ) ! 1 ( 1) 3! 1 2! 1 1! 1 !(1 n D n n n = − + − ++ −