排列組合專題之錯排問題

1、排列組合專題之錯排問題1993年的全國高考試題一改以前數(shù)學高考 “以知識立意” 命題思路， 開始明確提出 “以 能力立意”，這是數(shù)學高考改革的一項重要舉措，高考數(shù)學命題更加注重了對能力和素質的 考查，試題設計增加了應用性和能力型題目， 其中的 “賀卡問題” 就屬于這方面的一道好題。賀卡問題：同室四人各寫一張賀年卡，先集中起來，然后每人從中拿一張別人送的賀 年卡，則四張不同的賀年卡不同的分配方式有：A、6 種 B、9 種 C、11 種 D、23 種 這個問題的情境新穎，無法直接套用公式、法則，主要考查分類或分步計數(shù)原理或從 反面考慮（排除法） 的思想方法，考查分析問題與解決問題的能力，本題以組合

2、數(shù)學中著名 的“錯排問題”為背景，用貼近學生身邊生活的“賀卡”來設計問題，顯得較恰當。其實， 實際生活中的“錯排問題”有多種多樣，如信封中裝錯信件或坐錯座位等等。錯排問題：有 n個正整數(shù) 1， 2，3， n，將這 n個正整數(shù)重新排列，使其中的每一 個數(shù)都不在原來的位置上，這種排列稱為正整數(shù)1，2，3， n 的錯排，問這 n 個正整數(shù)的排個數(shù)是多少？設這 n個正整數(shù)的錯排個數(shù)為 an，為了探求 an的表達式， 我們先從最特殊的情形入手。當 n=1 時，由于只有一個數(shù) 1 ，不可能有錯排，所以 a1=0.當 n=2 時，兩個數(shù)的錯排是唯一的，所以a2=1.當 n=3 時，三個數(shù) 1、2、3只有 2

3、、3、1和 3、 1、 2兩種錯排，所以 a3=2.當 n=4 時，四個數(shù) 1、2、3、4 的錯排有： 2、1、4、3；2、3、4、1；2、4、1、3；3、 1、4、2；3、4、2、1；4、1、2、3；4、3、1、2；4、3、2、1，共有 9 種錯排，所以 a4=9.剛才提到的 93 年高考試題賀卡問題，實際上求的就是a4 等于多少？上面使用的是枚舉法，當 n 較大時，這種方法是很麻煩的、難以解決問題的，必須另 辟蹊徑，現(xiàn)在考慮用排除法求出 1、2、3、4 這四個正整數(shù)的錯排的種數(shù)，從中摸索出規(guī)律。對于四個正整數(shù) 1、2、3、 4，這四個數(shù)的全排列數(shù)為 4！。 有一個數(shù)不錯排的情況應排除，由于

4、 1排在第 1位的有 3！種， 2排在第 2位的有 3！ 種， 4 排在第 4位的有 3！種，所以共應排除 43！種。然而在排除有一個數(shù)不錯排的情況時，把同時有兩個數(shù)不錯排的情況也排除了，應予 以補上，由于 1、2 分別排在第 1、第 2 位上的情況共有 2！種，同理 1、3 分別排在第 1、 第 3 位上的情況也有 2！種，這四個數(shù)中同時有兩個數(shù)不錯排的情況共有種，所以應24!補上 C42 2! 種。在補上同時有兩個數(shù)不錯排的情況時，把同時有三個數(shù)不錯排的情況42!也補上了，應予以排除，四個數(shù)中有1、2、3不錯排， 1、2、4 不錯排， 1、3、4不錯排和1 4!2、3、4 不錯排共 C14

5、種情況，所以應排除 C41 1! 種。4 4 3!在排除同時有三個數(shù)不錯排的情況時，把同時有四個數(shù)不錯排的情況也排除了，所以 應補上同時有四個數(shù)不錯排的情況僅1、2、3、4 這一種。由 a44!2!4! 4!43! 44! 以及 a33!2!3!3!，a21 2! ，我們猜想 n 個正整數(shù) 1、2 、3、 2!4、 n 的錯排的種數(shù) an 的表達式為nan=(k2k n!1)k kn!，面我們來證明這個表達式。4!4!4!4!4!a4 4! 4 3!194 2!3!2!3!4!綜上所述，般來說，正整數(shù) 1、2、3、n的全排列有 n！種，其中第 k 位是 k 的排列有（n-1）！，當 k 取 1

6、、 2、3、 n 時，共有 n( n-1)！種排列，由于是錯排，這些排列應排除，但是此時把同時有兩個數(shù)不錯排的排列多排除了一次， 應補上； 在補上時， 把同時有三個數(shù)不錯排的排列多補上了一次，應排除；繼續(xù)這一過程，得到錯排的排列種數(shù)為ann!n!2!3!( 1)n nn!，1于是有 bn bn 1(bn 1bn2)n從而可求 bn ，所以 ann!n!2!3!(n 1)(n1)! bn 1(n1)! bn 2 ,111n1( )()()(b2b1) ( 1)n ，nn13n!nn!( 1)n。n!n!n!n!n n!n!n!n n! n k n!an n!( 1)n( 1)，即 an( 1)n

7、 1!2!3!n!2!3!n! nk 2 k!計數(shù)是一種常見的數(shù)學問題，涉及計數(shù)問題的另一種思路是運用遞推方法，應該說， 利用遞推方法是解決計數(shù)問題的重要方法，下面我們再用遞推關系求an 的值。由題意 a1=0，a2=1，當 n3 時，在錯排中 n 必不在第 n 位，設 n放在第 k 位上( 1k n-1 )，則第 n 位上有兩種可能：(1)如果第 n 位上不是 k，那么把第 n 位看作第 k 位，將 n 以外的 n1 個數(shù)進行錯排， 錯排個數(shù)是 an-1；(2)如果第 n位上是 k，那么除 n和 k以外的 n2個數(shù)的錯排是 an-2，所以 n在第 k位上的錯排數(shù)共有 an-1 an-2，由于 k可取 1、2、3、4、 n1共 n1種取法，所以 n 個數(shù)的錯排個數(shù) an (n 1)(a