复旦大学：《离散数学 Discrete Mathematics（上）》英文课件（赵一鸣）10/30

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

Xx2,X=xi+i2+…+i=yr r-combination ofs Definition 1: The generating function for the sequence a0s2a1y…,any… of real numbers is the infinite series f(X)=a0+a1x+a2x2+…+anx"+…, an ∑ax=∑ b,x' if only if a;=b; for all i=0,1,…n, i=0 i=0

▪ x i1x i2…xik= xi1+i2+…+ik=xr ▪ r-combination of S ▪ Definition 1: The generating function for the sequence a0 ,a1 ,…,an ,… of real numbers is the infinite series f(x)=a0+a1x+a2x 2+…+anx n+…, and    =  = = 0 i 0 i i i i i a x b x if only if ai=bi for all i=0,1, …n, …

We can define generating function for finite sequences of real numbers by extending a finite sequences a0 1r,gan into an infinite sequence by setting an+=0, an+2=0, and so on. The generating function f(x) of this infinite sequence a is a polynomial of degree n since no terms of the form a; x, with i>n occur, that is f(x=ao+,+ x2+.tanx

▪ We can define generating function for finite sequences of real numbers by extending a finite sequences a0 ,a1 ,…,an into an infinite sequence by setting an+1=0, an+2=0, and so on. ▪ The generating function f(x) of this infinite sequence {an } is a polynomial of degree n since no terms of the form ajx j , with j>n occur, that is f(x)=a0+a1x+a2x 2+…+anx n

Example: (1)Determine the number of ways in which postage of r cents can be pasted on an envelope using 1 1-cent, 1 2-cent, 1 4-cent, 1 8-cent and 1 16-cent stamps (2)Determine the number of ways in which postage of r cents can be pasted on an envelope using 2 1-cent, 3 2-cent and 2 5 cent stamps Assume that the order the stamps are pasted on does not matter Let ar be the number of ways in which postage of r cents. Then the generating function f(x)of this sequence a is (1)f(x)=(1+x)(1+x2)(1+x4)(1+x3)(1+x (2)f(x)=(1+x+x2)(1+x2+(x2)2+(x2)3)(1+x5+(x5)2)) 1+x+2x2+x3+2x4+2x5+3x6+3x7+2x8+2x9+2x10+3x1 +3x12+2x13+2x14+x15+2x16+x17+x18

▪ Example: (1)Determine the number of ways in which postage of r cents can be pasted on an envelope using 1 1-cent,1 2-cent, 1 4-cent, 1 8-cent and 1 16-cent stamps. ▪ (2)Determine the number of ways in which postage of r cents can be pasted on an envelope using 2 1-cent, 3 2-cent and 2 5- cent stamps. ▪ Assume that the order the stamps are pasted on does not matter. ▪ Let ar be the number of ways in which postage of r cents. Then the generating function f(x) of this sequence {ar } is ▪ (1)f(x)=(1+x)(1+x2 )(1+x4 )(1+x8 )(1+x16) ▪ (2)f(x)=(1+x+x2 )(1+x2+(x2 ) 2+(x2 ) 3 )(1+x5+(x5 ) 2 )） ▪ =1+x+2x2+x3+2x4+2x5+3x6+3x7+2x8+2x9+2x10+3x11 +3x12+2x13+ 2x14+x15+2x16+x17+x18

Example: Use generating functions to determine the number of r-combinations of multiset s=oo.a1,oo a2,..., 00.ak. Solution: let b be the number of r- combinations of multiset s And let generating functions of (b be f(y (1+y+y2+..)k=?f(y) ∑C(k+r-1,r)y (1-y)

▪ Example: Use generating functions to determine the number of r-combinations of multiset S={·a1 ,·a2 ,…, ·ak }. ▪ Solution: Let br be the number of r￾combinations of multiset S. And let generating functions of {br } be f(y)， ▪ (1+y+y2+…)k=? f(y)   = = + − − = 0 ( 1, ) (1 ) 1 ( ) r r k C k r r y y f y