|A1∩A2∩?∩Am| = |Z|－

?i?1m| Ai |+

?i?j| Ai∩Aj |－

i?j?k?|Ai∩Aj∩Ak|+?+(-1)m| A1∩A2∩?∩Am |

= ???r??－??1????r??+??2????????????r?n?n?m??m??n?1??m??n?2??m??n?3?m???????－+?+(-1)??3??r??r??

???????i?m??n?i? = ?(?1)??i????r??

i?0????m?n?m?因此，我们得到 ：??n?r??=

??3.33.试证：

m??n?i?i??(?1)??i????r??。

i?0????m(a)D(n,r,k)=????D(n-k,r-k,0)

(b)D(n,r,k)=D(n-1,r-1,k-1)+(n-1)D(n-1,r-1,k)+(r-1){D(n-2,r-2,k)-D(n-2,r-2,k-1)}

其中D(n,r,-1)定义为0。

?r??k??n?(c)D(n,n,k)=nD(n-1,n-1,k)+(-1)??k??

??n-k

(d)????D(n,r,k)=????D(n-t,r-t,k-t)，t ≥ 0 (e)D(n,r,k)=rD(n-1,r-1,k)+D(n-1,r,k)，其中r < n

?k??t??r??t??r?(f)D(n,n-r,0) =???i??D(n-i,,r-i,0)，其中D(n,n,0) =Dn

i?0??rD(n,r,k)是3.6节中的推广了的错排。

[证].(a)从1～n个数中取出r个元素进行r位排列，要求其中有k个位满足条件：ai=i的方案(其方案数为D(n,r,k))；相当于在r位中选出k个位，让这k个位满足条件：ai=i(这有????种选法)，其余的r-k个位从剩下的n-k个数中选数做完全的错排(无一位满足条件ai=i)(这有D(n-k,r-k,0)种排法)的方案(根据乘法原理，其方案数为????D(n-k,,r-k,0))。所以

?r??k??r??k?D(n,r,k)=????D(n-k,,r-k,0)。

(b)从1～n个数中取出r个元素进行排列，要求其中有且仅有k个位满足条件：ai=i，其方案数为D(n,r,k)；根据a1=1和a1?1可分成两个部分：

1)若a1=1，即数1排在第一位，则此种方案其余部分为从2～n这n-1个数中取出r-1个元素进行排列，要求其中有k-1个位满足条件：ai=i，其方案数为D(n-1,r-1,k-1)；

【第 25 页 共 42 页】

?r??k?

2)若a1?1，即数1不排在第一位，于是可设a1=i0(i0=2,3,?,n)，即数i0排在第一位，根据2? i0? r和r+1? i0? n此种方案可分成两个部分：

i)若r+1? i0? n，即数i0排在第一位，有n-r种选法，此种方案其余部分为从1,2,?,

r ,r+1,?,i0-1,i0+1,?,n这n-1个数中取出r-1个元素进行排列，要求其中有k个位满足条件：ai=i，其选法为D(n-1,r-1,k)；于是，根据乘法原理，此种方案有(n-r)D(n-1,r-1,k)个。

ii)若2? i0? r，即数i0排在第一位，有r-1种选法，并且数i0不排在第i0位，此种

方案其余部分所构成的方案集，我们设其为A

A：从1,2, ?,i0-1,i0+1,?,r,r+1,?,n这n-1个数中取出r-1个元素进行排列的方案，要求其中有k个位满足条件：ai=i (2? i ? r且 i ? i0)。

为了计算|A|，我们来考虑另一方案集B

B：从2,?,r,r+1,?,n这n-1个数中取出r-1个元素进行排列的方案，要求其中有k个位满足条件：ai=i (2? i ? r)。

显然，|B| = D(n-1,r-1,k)。但是方案集B比方案集A，少了取数集为{1,j1,?,jr-2}(这里：ji? i0(1? i ? r-2))的方案，这种方案有D(n-2,r-2,k)个，但是又多了不动位集为{ai0= i0,ai1= i1,?,aik?1= ik-1}的方案，这种方案有D(n-2,r-2,k-1)个。所以，

|A|=|B|+D(n-2,r-2,k)-D(n-2,r-2,k-1) = D(n-1,r-1,k)+D(n-2,r-2,k)-D(n-2,r-2,k-1)。 因此，根据乘法原理，这类方案总数为

(r-1)|A|=(r-1){D(n-1,r-1,k)+D(n-2,r-2,k)-D(n-2,r-2,k-1)}。 最后，按加法原理，我们有

D(n,r,k) =D(n-1,r-1,k-1)+(n-r)D(n-1,r-1,k)

+(r-1) {D(n-1,r-1,k)+D(n-2,r-2,k)-D(n-2,r-2,k-1)}

=D(n-1,r-1,k-1)+(n-1)D(n-1,r-1,k)+(r-1){D(n-2,r-2,k)-D(n-2,r-2,k-1)}。

(c)D(n,n,k)为将1～n这n个数进行全排列，要求其中有k个位满足条件：ai=i的方案数；

?n?相当于在n位中选出k个位，让这k个位满足条件：ai=i，这有??k??种选法，其余的n-k个

??位用剩下的n-k个数做完全的错排(无一位满足条件ai=i)，有Dn-k种错排，于是，根据乘法原理，有????Dn-k种方案。所以

?n??k??n?D(n,n,k)=??k??Dn-k。

??根据ppt第二章§9定理2.9.1(2)Dn-nDn-1=(-1)n 可得Dn-k= (n-k)Dn-k-1+(-1)n-k 于是，有

【第 26 页 共 42 页】

D(n,n,k)=????Dn-k

?n??k?n-k

??= (n-k)?D-k-1+(-1)n?????

?n??k??n??k?nn!n-k???= (n-k)Dn-k-1+(-1)??? k(n?k)!k!??= n

?n?(n?1)!?Dn-k-1+(-1)n-k? ??k(n?k?1)!k!??n?n?1?n-k?????= n?Dn-k-1+(-1)???? kk????=nD(n-1,n-1,k)+(-1)n-k????。

(d)从1～n个数中取出r个元素进行r位排列，要求其中有k个位满足条件：ai=i(有D(n,r,k)

?n??k??k?种排法)，然后再从这k个位中选取t个位打上标记*(有??t??种选法)的方案(根据乘法原理，

??其方案数为????D(n,r,k))；相当于先在r位中选出t个位让其满足条件：ai=i并打上标记*(有

?k??t??r???t??种选法)，而后在剩下的n-t个数中取出r-t个元素进行r-t位排列，要求其中有k-t个??位满足条件：ai=i(有D(n-t,r-t,k-t)种排法)的方案(根据乘法原理，其方案数为

?r???t??D(n-t,r-t,k-t))。所以 ???k??r????t?D(n,r,k)=??t??D(n-t,r-t,k-t)。 ????(e)从1～n个数中取出r个元素进行r位排列，要求其中有k个位满足条件：ai=i，其方

案数为D(n,r,k)；因为r < n，根据所选的r个元素中含数n和不含数n可分成两个部分：

1)若含数n，则数n可排在这r个位的任一位上，有n种排法，此种方案其余部分为从1～n-1这n-1个数中取出r-1个元素进行r-1位排列，要求其中有k-1个位满足条件：ai=i，其方案数为D(n-1,r-1,k-1)，于是，根据乘法原理，其方案数为rD(n-1,r-1,k)；

2)若不含数n，则此种方案为从1～n-1这n-1个数中取出r个元素进行r位排列，要求其中有k个位满足条件：ai=i，其方案数为D(n-1,r,k)；最后，按加法原理，我们有

D(n,r,k)=rD(n-1,r-1,k)+D(n-1,r,k)。 (f)

【第 27 页 共 42 页】

D(n,n-r,0) =

?r????i??D(n-i,,r-i,0)，其中D(n,n,0) =Dn 。 i?0??r3.34.n?N，设Pn表示在{1,2,?,n}的全排列中，排除了k，紧随以k+1，k=1,2,?, k+1，试证：

Pn= Dn+Dn-1，n?N 。

3.35.令Dn(k) = D(n,n,k)，试证 (a)Dn(k) =????Dn-k

?n??k??n??n??n?(b)??1??D1+??2??D2+?+??n??Dn = n! ??????(c)(k+1)Dn+1(k+1) = (n+1)Dn(k)。 3.36. 令Dn(k) = D(n,n,k)，试证 (a)

?kD(k) = n!

n

k?0n(b)Dn(0)－Dn(1) = (-1)n (c)

?(k?1)k?0nn2Dn(k) = n!

(d)

?(k?1)?(k?r?1)D(k) = n!，其中r ? n 。

n

k?03.37.试证：

(a)?(mn) = ?(m)?(n) (条件：(m,n)=1,即m,n互素)

(b)对于素数pi，i ? 1, ?(pi)= pi-pi-1

[证]. (a)可设 m=p11p22?pkk (其中：?i?1 (1≤ i ≤ k) )

n=q11q22?qll (其中：?j?1 (1≤ j ≤ l) )

由于 (m,n)=1，即，m,n互素，故素数p1,p2,?,pk与素数q1,q2, ?,ql没有相同的，即，对任何i,j(1≤ i ≤ k，1≤ j ≤ l)，都有 pi≠qj 。 故此 ?(mn) = mn(1－

??????111111)(1－)?(1－)(1－)(1－)?(1－) p1p2pkq1q2ql111111)(1－)?(1－)]·[n(1－)(1－)?(1－)] p1p2pkq1q2ql = [m(1－

= ?(m)?(n) 。

若 (m,n)?1，即，m,n不互素，则此等式不成立。例如，若

【第 28 页 共 42 页】