不動點與組合問題（學生版）

不動點與組合問題第一節(jié)不對號入座與全錯位排列一、問題把n個編號為的球放入n個編號為的盒子中，要求每個盒子中只放一個球，且球的號碼與盒子的編號數(shù)均不相同，試求有多少種不同的放法種數(shù)？這個問題就相當于n個自然數(shù)的全錯位排列問題.不妨設這種不同的放法種數(shù)有種，它可以分兩步完成：第一步放編號為1的球，共有種放法，此時不妨把編號為1的球放在編號為的盒子里，再安排第i號球的位置，有兩種情況：①第i號球放在第1個盒子中，剩余的個球要放在個盒子中，依然要求是號碼均不相同，故種放法；②第i號球不放在第1個盒子中，此時如同個球要放在個盒子中，且號碼均不相同，故有方法數(shù)為種.所以，一般地，我們得到遞推公式，①其中.利用這個公式，我們可以解決這類錯位排列問題.二、探求通項公式由遞推公式①及，可得：，上式兩邊同乘以得：②于是可得：，，，，將上述個式子累加，得：所以，故.評注由遞推公式①得到遞推公式②是求解的關鍵，這也是處理復雜遞推數(shù)列問題的難點所在.例1同室四人各寫一張賀年卡，先集中起來，然后每人從中拿一張別人送出的賀年卡，則四張賀年卡不同的分配方式有（）A.6種.B.9種.C.11種.D.23種.分析此題是全錯位排列問題，我們可以應用公式來進行解題.解析由遞推公式①及，可得.故選B.例2五個瓶子都貼了標簽，其中恰好貼錯了三個，貼錯的可能情況共有（）種.A.6B.10C.12D.20分析此題也是錯位重排但不是全部錯位，我們可以部分應用錯位重排來進行解題.解析分步進行：第一步，選出三個瓶子，這三個瓶子恰好貼錯了，有種；第二步，這三個瓶子滿足錯位重排，所以對應的公式數(shù)據(jù)應該是2.最后根據(jù)乘法原理，共有種.故選D.例3某人給6個不同的人寫了6封信，每人一份，并準備了6個寫有收信人地址的信封，問有多少種投放信箋的方法，使得每份信箋和信封上的收信人都不相同？分析：此題是全錯位排列問題，我們可以應用公式來進行解題.解析由遞推公式①及，可得：，，.故共有265種投放信箋的方法，使得每份信箋和信封上的收信人都不相同.三、問題的推論與探究引理用表示n個不同元素全錯位排列的方法數(shù)，則n個不同元素全錯位排列的方法數(shù)滿足.（1）下面用第二數(shù)學歸納法給出引理的一般性證明.證明（1）易知當時，，滿足，式（1）成立；當時，，滿足，式（1）成立.（2）假設時，式（1）成立，即k個元素全錯位排列的方法數(shù)的遞推關系為，則當時，設全錯位排列的元素為.在k個元素全錯位排列的基礎上，個元素全錯位排列后，它們?nèi)e位排列的方法分為2類：①與互調(diào)位置，其余元素全錯位排列，方法數(shù)為；②在的位置上，但不在的位置上，其余元素仍然錯位排列.這樣的排列，相當于將k個元素的每一個全錯位排列中的元素置換了一遍.k個元素的每一個全錯位排列是k個元素，因此該類全錯位排列的方法數(shù)為.綜上所述，，又，故.即當時，式（1）成立.因此，n個元素全錯位排列的方法數(shù)的遞推關系為.定理用表示n個不同元素所有的全錯位排列的方法數(shù)，則當時，；當時，.n個不同元素排成一列，記下每個元素的編號，重新排列后，有以下結(jié)論：推論1某i個元素（特定）現(xiàn)在的編號與原編號一致，個元素現(xiàn)在的編號與原編號錯位的排列方法數(shù)為.推論2i個元素（不特定）現(xiàn)在的編號與原編號一致，個元素現(xiàn)在的編號與原編號錯位的排列方法數(shù)為.推論3某i個元素（特定）在原有的位置上互相全錯位，另個元素在原有的位置上互相全錯位，這樣的排列數(shù)為.推論4i個元素（不特定）在原有的位置上互相全錯位，另個元素在原有的位置上互相全錯位，這樣的排列數(shù)為.例1同寢室4人各寫一張賀年卡，先集中起來，然后每人從中拿一張別人送出的賀卡，則4張賀卡不同的分配方式有_________種.解該題屬于4個元素的全錯位問題.由定理得，故分配方式有9種.例2設編號為1，2，3，4，5的5個球及編號為1，2，3，4，5的5個盒子，一個盒子內(nèi)放一球，恰有2個球的編號與盒子編號相同，則投放種數(shù)有多少？解“恰有2個球的編號與盒子編號相同”等價于“恰有3個球的編號與盒子編號不同”.由推論2得，投放種數(shù)為.例3編號為1，2，3，4，5的5個人，分別坐在編號為1，2，3，4，5的座位上，則至多2個號碼一致的坐法有多少種？解法1（直接法）至多2個號碼一致，分3種情況：（1）“恰2個一致”等價于“恰3個錯位”，；（2）“恰1個一致”等價于“恰4個錯位”，；（3）沒有一致”等價于“5個全錯位”，.從而.解法2（間接法）無任何限制條件時，.“恰有3個號碼一致”等價于“恰有2個錯位”，；“恰有4個號碼一致”與“恰有5個號碼一致”的坐法屬同一種情況，故.從而.例4有4位同學在同一天的上、下午參加“身高與體重”、“立定跳遠”、“肺活量”、“握力”、“臺階”5個項目的測試，每位同學上、下午各測試一個項目，且不重復.若上午不測“握力”項日，下午不測“臺階”項目，其余項目上、下午都各測試一人，則不同的安排方式共有多少種？解4位同學上午測試“身高與體重”、“立定跳遠”、“肺活量”、“臺階”4個項目的方法數(shù)為種.下午測試的方法分為2類：（1）4位同學測試的項目仍然是上午的4個項目，方法數(shù)是4個元素的全錯位排列數(shù)，只需將每一個全錯位排列中的“握力”項目替換為“臺階”，方法數(shù)為；（2）若測“臺階”的同學剛好測“握力”項目，則方法數(shù)為.故下午測試的方法數(shù)共有種.從而上、下午不同的安排方式共有種.第二節(jié)組合不動點組合不動點問題的反面提法是“擾排問題”定義：設集合是集合的一個排列，若，則稱k為變換F的一個組合不動點，我們用表示n個元素有k個組合不動點的排列個數(shù)，表示有k個動點的排列個數(shù).顯然有，.定理1..證明：所有的排列數(shù)問題可分二步思考.首先，從n個元素中選出k個元素排在k個位置上，使每個元素的編號與它所在位置的號碼一致（不動），共有種不同的排法，其次，將其余個元素排在是個位置上，使每個元素的編號與它所在位置的號碼不一致（全動），有種排法，由乘法原理，故原命題得證.定理2..證明：.定理3..證明：考慮第k號元素正好放在第k號位置上，顯然，其余個元素放在個位置上的所有排列數(shù)為，且和式共有項，所以而的排列數(shù)為，和式共有項.所以同理，的排列數(shù)為，和式共有項.所以顯然，，且n個元素的全排列為.由容斥原理有：定理4.證明：因為n個元素的全排列個數(shù)為.另一方面考慮可分成恰好零個組合不動點，恰好一個組合不動點，恰好兩個組合不動點，…，恰好n個組合不動點，由加法原理有：，類似地可得到定理5.從編號為的n個元素，取出k個（）元素排在編號為的位置上（每一個位置只允許排一個元素），有k個動點的排列個數(shù)為：.當時，即定理3.故定理5可視為定理3的推廣.例1.設有編號1，2，3，4，5的五個球和編號為1，2，3，4，5的五個盒子.現(xiàn)將這五個球投入這五個盒子內(nèi)，要求每個盒子投放一個球，求以下幾種情況的投放方法數(shù).①恰好有兩個球的編號與盒子編號相同；②恰好沒有兩個球的編號與盒子編號相同；③至多有兩個球的編號與盒子編號相同；④至少有兩個球的編號與盒子編號相同.解：①②③④或.例2.同室4人各寫1張賀年卡，先集中起來，然后每人從中拿1張別人送出的賀年卡，問：4張賀年卡有多少種不同的分配方法.解：本題即求四個元素的無不動點排列個數(shù)..該題與一道波蘭數(shù)學競賽（1960～1961年）題類似，其原題為：“某人給6個不同的收信人寫了6封信，并且準備了6個寫有收信人地址的信封.問：有多少種裝入信箋的方法，使每一信箋與信封上的收信人都不相符？”由題意即得（種）.以上兩題實際上均為著名的BernoulliEuler裝錯信箋問題的特殊情況.例3.P為集合的一個排列，令為的無不動點的排列個數(shù)，為恰好有一個動點的排列個數(shù)，證明：.證明：因為所以.例4.設表示n個元素中有k個不動點的所有排列的種數(shù).求證：.證明：定理6.編號為的n個元素排在編號為的位置上（每個位置只排一個元素）.則指定某個元素為動點的排列個數(shù)為：證明：若指定某個元素中的第i個元素，正好在第i個位置上，其他個元素放在個位置上，則所有的排列數(shù)為.而指定的某k個元素中的第i和j個元素恰好在第i和j的位置上，其他個元素全排列時，所有的排列數(shù)為.同理，若指定的k個元素其編號都排在與其編號相同的位置上時，有種排法.由容斥原理得：例5.將編號為1，2，3，…，9的九個球放入編號為1，2，3，…，9的九個盒內(nèi).要求每盒放一個球，且規(guī)定奇數(shù)k號的球不許放在奇數(shù)k號盒內(nèi)，這樣的投放方法有多少種？解：本題是求指定五個元素為動點的排列個數(shù)，利用定理6有：（種）例6.上屆獲得前n名的球隊參加本屆爭奪前n名的比賽.如果不設并列名次，問：若沒有一個隊取得的名次恰好緊接在上屆比他高一個名次的球隊之后，那么比賽結(jié)果有多少種可能？解：設上屆獲得前n名的n個球隊按名次的一個排列為，這里不妨將球隊號也按上述順序排列，由題意可知，本屆比賽出現(xiàn)的名次不可能有以下排列：.實際上就是，編號為的n個元素排在編號為的位置上（每個位置只排一個），指定個元素為動點的排列個數(shù)為：【強化訓練01】1．如圖，一環(huán)形花壇分成四塊，現(xiàn)有4種不同的花供選種，要求在每塊里種1種花，且相鄰的2塊種不同的花，則不同的種法總數(shù)為A．96 B．84 C．60 D．48【強化訓練02】2．某人有4種顏色的燈泡（每種顏色的燈泡足夠多），要在如圖所示的6個點A、B、C、A1、、B1、C1上各裝一個燈泡，要求同一條線段兩端的燈泡不同色，則每種顏色的燈泡都至少用一個的安裝方法共有種（用數(shù)字作答）.【強化訓練03】3．如圖，用四種不同顏色給圖中的A,B,C,D,E,F六個點涂色，要求每個點涂一種顏色，且圖中每條線段的兩個端點涂不同顏色，則不同的涂色方法用A．288種 B．264種 C．240種 D．168種【強化訓練04】4．有4位同學在同一天的上、下午參加“身高與體重”、“立定跳遠”、“肺活量”、“握力”、“臺階”五個項目的測試，每位同學上、下午各測試一個項目，且不重復.若上午不測“握力”項目，下午不測“臺階”項目，其余項目上、下午都各測試一人.則不同的安排方式共有______________種（用數(shù)字作答）.【強化訓練05】5．將字母a,a,b,b,c,c,排成三行兩列，要求每行的字母互不相同，每列的字母也互不相同，則不同的排列方法共有A．12種 B．18種 C．24種 D．36種【強化訓練06】6．將用1～6編號的六張卡片，插入用1～6編號的六個盒子里，每只盒子插一張，求：(1)使每一卡片的號碼與所在盒子號碼都不同的插法總數(shù)；(2)恰好有3張卡片號碼與所在盒子號碼相同的插法總數(shù).【強化訓練07】7．n個學生參加一次聚會，每人帶一張賀卡和一件禮物，會后每個