复旦大学：《离散数学》PPT教学课件（赵一鸣）09/28

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 0x12,0x22,1x35? ▪ 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 ▪ 0x12,0x22, 0x3 '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: ▪ i11,i22,…,inn. ▪ We denote by Dn the number of derangements of {1,2,…,n}. ▪ Theorem 4.15：For n1, ) ! 1 ( 1) 3! 1 2! 1 1! 1 !(1 n D n n n = − + − ++ −

Proof: Let s=(1, 2,.., n andx be the set of all permutations of s. Then x=n For j=1, 2,e., n, let pi be the property that in a permutation,j is in its natural position. Thus the permutation i1,i2, ...,in of s has property p provided i=j. A permutation of s is a derangement if and only if it has none of the properties p1p2…pn Let ai denote the set of permutations of s with property p; (j=1, 2,., n)

▪ Proof: Let S={1,2,…,n} and X be the set of all permutations of S. Then |X|=n!. ▪ For j=1,2,…,n, let pj be the property that in a permutation, j is in its natural position. Thus the permutation i1 ,i2 ,…,in of S has property pj provided ij=j. A permutation of S is a derangement if and only if it has none of the properties p1 ,p2 ,…,pn . ▪ Let Aj denote the set of permutations of S with property pj ( j=1,2,…,n)

Example: (dEtermine the number of permutations of (1, 2, 3, 4, 5, 6, 7, 8, 9 in which no odd integer is in its natural position and all even integers are in their natural position. (2) Determine the number of permutations of 1, 2, 3, 4, 5, 6, 7, 8, 9 in which four integers are in their natural position

▪ Example:(1)Determine the number of permutations of {1,2,3,4,5,6,7,8,9} in which no odd integer is in its natural position and all even integers are in their natural position. ▪ (2) Determine the number of permutations of {1,2,3,4,5,6,7,8,9} in which four integers are in their natural position

3. Permutations with relative forbidden position A Permutations of (1, 2,e., n with relative forbidden position is a permutation in which none of the patterns i, i+l(i=l, 2,.., n)occurs. We denote by Qn the number of the permutations of (1, 2,, n with relative forbidden position Theorem4.16:Forn≥1, Qn=n!-C(n-1,1)(n-1)+C(n-1,2)(n-2)!-…+(-1)m1 C(n-1,n-1)1!

▪ 3. Permutations with relative forbidden position ▪ A Permutations of {1,2,…,n} with relative forbidden position is a permutation in which none of the patterns i,i+1(i=1,2,…,n) occurs. We denote by Qn the number of the permutations of {1,2,…,n} with relative forbidden position. ▪ Theorem 4.16：For n1, ▪ Qn=n!-C(n-1,1)(n-1)!+C(n-1,2)(n-2)!-…+(-1)n-1 C(n-1,n-1)1!

Proof: Let s=(1, 2,.o, n and x be the set of all permutations of s. Then x=n j〔j+1),p(1,2,…,n-) Q=D,+D

▪ Proof: Let S={1,2,…,n} and X be the set of all permutations of S. Then |X|=n!. ▪ j(j+1), pj (1,2,…,n-1) ▪ Aj : pj ▪ Qn=Dn+Dn-1

4.6 Generating functions 4.6.1 Generating functions the number n of r-combinations of s equals nks), then Let s=(n, la,n2°a2y…,nk°ak},andn=n1+n2+ (1)0 when r>n (2)1 when r=n (3)N=C(k+r-l, r)when ni 2r for each i=1, 2,...,n (4)If r<n, and there is, in general, no simple formula for the number of r-combinations of s A solution can be obtained by the inclusion-exclusion principle and technique of generating functions 6-combination ajaja3a3a3a4

4.6 Generating functions ▪ 4.6.1 Generating functions ▪ Let S={n1 •a1 ,n2 •a2 ,…,nk •ak }, and n=n1+n2+…+nk=|S|，then the number N of r-combinations of S equals ▪ (1)0 when r>n ▪ (2)1 when r=n ▪ (3) N=C(k+r-1,r) when ni r for each i=1,2,…,n. ▪ (4)If r<n, and there is, in general, no simple formula for the number of r-combinations of S. ▪ A solution can be obtained by the inclusion-exclusion principle and technique of generating functions. ▪ 6-combination a1a1a3a3a3a4