n??n??n??n? 4.9 定义D0=1，证明：n!??D?D?D?????n??1??2??D0?0??1??2??n??n?证明：考虑到n个数的全排列包含错位排列和非错排，其中??Dk表
?k?示在n个数中任选k个，这个k个数构成了一个错排，而剩余的n-k个数还在原来的位置。
?n??n??n??n??n??n???????，显然n!???D0???D1???D2?...???Dn
?0??1??2??n??0??n?（另一种方法：组合分析法） 4.10证明：Dn满足：
?Dn?(n?1)(Dn?1?Dn?2) ??D1?0,D2?1 ｎ为整数且ｎ?３
证明：由定理4.3.1得
Dn?1?(n?1)!(1?111?...?(?1)n?1) 1!2!(n?1)!111n?2?(n?1)!(1??...?(?1))?(?1)n?1
1!2!(n?2)!Dn?2?(n?2)!(1??Dn?1?Dn?2111?...?(?1)n?2) 1!2!(n?2)!111n?2?(1??...?(?1))[(n?2)!?n]?(?1)n?11!2!(n?2)!111?...?(?1)n?2)?(?1)n?1(n?1)1!2!(n?2)!?(n?1)(Dn?1?Dn?2)?n!(1?
1111n?2n?1n1?(1??...?(?1)?(?1)?(?1))
1!2!(n?2)!(n?1)!n!4.11有10名女士参加一个宴会，每人都寄存了一顶帽子和一把雨伞，
而且帽子、雨伞都是互不相同的，当宴会结束的离开的时候，如果帽子和雨伞都是随机的还回的，那么有多少种方法使得每位女士拿到的物品都不是自己的？
解：由于帽子全部拿错和雨伞全部拿错是两个相互独立的事件，设帽
子全错为
1D10?10!(1?1111111111?????????) 1!2!3!4!5!6!7!8!9!10!21?D10雨伞全错为D10解
10!?10! ?D10?D?D?2e110210
4.13计算棋盘多项式R( )。 解： R( ) = x*R()+R( )
)
)]
=x*(1+3x+x2)+(1+x)*R(
= x3+3x2+x+(1+x)[xR()+R(
= x3+3x2+x+(1+x)[x(1+x)+(1+4x+2x2)] = 5x3+12x2+7x+1
4.14有A,B,C,D,E五种型号的轿车，用红、白、蓝、绿、黑五种颜色
进行涂装。要求A型车不能涂成黑色；B型车不能涂成红色和白色；C型车不能涂成白色和绿色；D型车不能涂绿色和蓝色；E型号车不能涂成蓝色，求有多少种涂装方案？ 解：A B C D E
红 白 蓝 绿 黑 1.若未规定不同车型必须涂不同颜色，则：
涂装方案4?3?3?3?4?432 2.若不同车型必须涂不同颜色，则：
禁区的棋盘多项式为： 1+8x+22x2+25x3+11x4+x5
所以：
5！-8*4！+22*3！-25*2！+11*1！-1=20