由調座位拓展研究不對號入座問題

在日常生活中，有許多事例都可以挖掘出比較深奧的數學知識，試看如下一例:

例1 某班教室里有座位6列，一段時間后對座位重新調配，按整列進行調換，要求大家調配后都不在先前的列，問調配方法有多少種?

這是與同學們學習生活密切相關的一道數學題，高中的同學在學完計數原理后可以解答，低年段的同學也可以由分類討論和枚舉法來完成，但是如果缺乏解題的思路，直接來處理此題，則難度較大，如何找到更好的方法呢?

一、分析思路

每列由一個同學作為代表，簡化以上問題，實質上就是:6個人，不對號入座，有多少種坐法?

初次接觸此類問題，難以尋找到適合的方法，此時不妨將人數減少，按2個人、3個人、4個人、5個人、6個人的順序階梯式遞進探索.我們將人員依次編號為①②③④⑤⑥.

十分明顯，2個人不對號入座，只有1種方法，而3個人不對號入座，有如下2種方法:

我們可以分兩步來考慮，先安排①號入座，有2種方法，再安排②③號入座，只有1種方法，由分步乘法原理，得3個人不對號入座，有2×1種方法.

計算4個人不對號入座時，先安排①號入座，有3種方法，再安排②③④號入座.例如①→2(如右圖所示)，此時②號→1時，③④號入座相當于2個人不對號入座，只有1種方法;②號不入座1號位時，此時1號位可相當于2號位，即變成了②③④號3個人不對號入座，有2×1種方法.

所以，4個人不對號入座，有3×(1+2×1)=9種方法.按同樣的思路，可以得到:

5個人不對號入座，有4×[2×1+3×(2+1)]=44種方法;

6個人不對號入座，有5×[3×3+4×(2+3×3)]=265種方法.

以上思路分析，給我們展示了研究數學問題的兩個過程，一是將實際問題抽象出數學模型，將問題加以簡化;二是將研究的維數降低，由易至難來探索解決問題的方法.

二、探索遞推

由2、3、4、5、6個人不對號入座的結論，我們不難發現這類不對號入座問題的一個遞推公式.設n個人不對號入座共有an種方法，則不同人數的坐法數對應于數列{an}.易知a1=0，a2=1，從前面的結論可歸納出:an=(n-1)(an+2+an-1)(n≥3).這一結論僅是一種歸納猜想，如何證明這一結論的正確性呢?

在這里，我們將上述不對號入座問題，變換一下問題的背景，以便更透徹地理解這一類問題.

例2 現有1，2，3，…，n，n個編了號的小球和n個編了號的箱，一個球放在一個箱里且不對號，有多少種不同的方法?

解:設n個球時共有an種放法，則不同個數球的放法數對應于數列{an}.

分兩步考慮，先放①號球，①號球共n-1種放法. 不妨設將其放入2號箱中，此時剩下的n-1個球和n-1個箱(如圖1).

再放剩下的n-1個球. ②號球可放入1號箱，也可以放到其它箱中.當②號球放入1號箱中時，余下的n-2個球和n-2個小箱恰好一一對號(如圖2)，則余下的球共an-2種不同放法.

當②號球不放入1號箱時，②號球相當于①號球，那么這時n-1個球和n-1箱共有an-1種不同放法.

綜上可知，n個球的不對號入座方法為an=(n-1)(an-2+an-1)(n≥3).

遞推公式表述為:a1=0，a2=1，an=(n-1)(an-2+an-1)，n≥3，由a1=0，a2=1，則可得:

三、鏈接考題

不對號入座問題，又可稱為組合數學中的“錯排問題”，此類問題具有豐富的生活背景，深入研究與討論要利用容斥原理，當元素個數較少時，可考慮作為中學數學的考題.

例3 (1993年全國高考)同室4人各寫1張賀年卡，先集中起來，然后每人從中各拿1張別人送出的賀年卡，則4張賀年卡不同的分配方式有多少種?

解法一: 排出所有的分配方案.

(1)甲取得乙卡，分配方案如右圖，此時乙有甲、丙、丁3種取法，若乙取甲，則丙取丁、丁取丙，故有3種分配方案;

(2)甲取得丙卡，分配方案按甲、乙、丙、丁4人依序可取得賀卡如下:丙甲丁乙，丙丁甲乙，丙丁乙甲;

(3)甲取得丁卡，分配方案按甲、乙、丙、丁4人依序可取賀卡如下:丁甲乙丙，丁丙甲乙，丁丙乙甲.

由加法原理，共有3+3+3=9種.

解法二:分步法.

第一步甲取1張不是自己所寫的那張賀卡，有3種取法;第二步由甲取出的那張賀卡的供卡人取，也有3種取法;第三步由剩余兩人中任1個人取，此時只有1種取法;第四步最后1個人取，只有1種取法.

由乘法原理，共有3×3×l×1=9種.

點評 解答此例“賀卡問題”時，根本無法直接套用公式、法則，而是運用分類或分步計數原理，考查分析問題與解決問題的能力.題目的情境新穎，以組合數學中著名的“錯排問題”為切入點，用貼近同學身邊生活的“賀卡”為背景，問題的設計正是恰到好處.這一類生活中的“錯排問題”多種多樣，各類考試中也頻繁出現，題目也產生各種各樣.再看如下考題.

例4 (2007年遼寧.文12)將數字1，2，3，4，5，6拼成一列，記第i個數為ai(i=1，2，…，6)，若a1≠1，a3≠3，a5≠5，a1

A. 18 B. 30 C. 36 D. 48 (答案:B)

例5 (1991年上海高考)設有編號為1，2，3，4，5的五個球和編號為1，2，3，4，5的五個盒子.現將這五個球投放入這五個盒內，要求每個盒內投放一個球，并且恰好有兩個球的編號與盒子的編號相同，則這樣的投放方法總數有多少?(答案:20)

例6 (2004年湖北高考)將標號為1，2，3，…，10的10個小球排入標號為1，2，3，…，10的10個盒子里，每個盒內排一個小球，恰好3個球的標號與其在盒子的標號不一致的排入方法種數為()

A. 120B. 240C. 360D. 720

(答案:B)

例7 (北京宣武區2008年高三模擬)編號為1、2、3、4、5的五個人分別去坐編號為1、2、3、4、5的五個座位，其中有且只有兩個的編號與座位號一致的坐法是()

A. 10種B. 20種C. 30種D. 60種

(答案:B)

例8 (公務員考試復習題)五個瓶子都貼了標簽，其中恰好貼錯了三個，則錯的可能情況共有多少種?(答案:20)

例9 (上海地區MBA招生系統班數學精選300題P42第14題)兩名教師分別對6名學生面試，每位教師各負責一門課，每名學生面試時間固定為一節課時間，6名學生面試時間定于下周一的第1節至第6節課，兩門課的面試分別在901和902兩個教室進行. 試問共有多少種面試的順序?(答案:183600)

四、研究通項

上述不對號入座問題，我們也可以表述為:有n個正整數1，2，3，…，n，將這n個正整數重新排列，使其中的每一個數都不在原來的位置上，這種排列稱為正整數1，2，3，…，n的錯排，那么問這n個正整數的錯排個數是多少呢?

設這n個正整數的錯排個數為an，易知a1=0，a2=1. 當n≥3時，在錯排中n必不在第n位，設n放在第k位上(1≤k≤n-1)，則第n位上有兩種可能:

(1)如果第n位上不是k，那么把第n位看作第k位，將n以外的n-1個數進行錯排，錯排個數是;

(2)如果第n位上是k，那么除n和k以外的n-2個數的錯排是an-2.

所以n在第k位上的錯排數共有an-1+an-2，由于k可取1、2、3、4、…、n-1，共n-1種取法，所以n個數的錯排個數an=(n-1)(an-1+an-2)，其中n≥3.

根據以上遞推公式，我們再來探索數列{an}的通項.

為了研究的方便，設ak=k#8226;bk(k=1，2，…，n)，則b1=0，b2=.

當n≥3時，n#8226;bn=(n-1)[(n-1)#8226;bn-1+(n-2)#8226;bn-2]=(n-1)(n-1)#8226;bn-1+(n-1)#8226;bn-2，

即:n#8226;bn=(n-1)#8226;bn-1+bn-2，于是有bn-bn-1=-(bn-1-bn-2)=…=(-)(-)…(-)(b2-b1)=(-1)n#8226;，

由累加法，可求得bn=-+…+(-1)n#8226;，

所以，an=n#8226;bn=n#8226;[-+…+(-1)n#8226;]，也可表示為an=(-1)k.

以上推導，通過分析遞推公式的特點，巧妙地構造出an的一種形式，經歷適當代數變形求得an.其實，還有一條捷徑來分析與求解，試看如下過程:

一般來說，正整數1、2、3、…、n的全排列有n種，其中第k位是k的排列有(n-1)，當k取1、2、3、…、n時，共有n×(n-1)種排列.由于是錯排，這些排列應排除，即得n-，但是此時把同時有兩個數不錯排的排列多排除了一次，應補上，即得n-+.在補上時，把同時有三個數不錯排的排列多補上了一次，應排除，即得n-+-;…繼續這一過程，得到錯排的排列種數為:an=n-+-+…+(-1)n=-+…+(-1)n，即an=(-1)k.

根據通項公式，我們可計算出:a2==1;a3=-=2;a4=-+=9;a5=-+-=44;…

五、追溯歷史

錯位排列問題是一個十分古老的問題，最初形式是“裝錯信封問題”，大意如下:一個人寫了n封不同的信及相應的n個不同的信封，他把這n封信都裝錯了信封，問都裝錯了信封的裝法有幾種?

這一問題由當時最有名的數學家約翰#8226;伯努利(Johann Bernoulli，1667-1748)的兒子丹尼爾#8226;伯努利(Danid Bernoulli，1700–1782)提出來，被著名數學家歐拉(Leonhard Euler，1707–1783)稱為“組合數學論”的一個妙題，將其表述為:n個有序元素，全部改變其位置的排列數是多少?所以稱之為“錯位”問題.大數學家歐拉等對此都有所研究，歐拉獨立獲得了錯位排列數的遞推公式和通項公式.

由錯位排列發展是限位排列問題，比如一個經典問題是“夫妻入座問題”:晚宴上，n對夫妻按以下規則坐入2n個座位，男女相間，夫婦不鄰，那么這樣的入座方法數有多少?在19世紀末20世紀初，有許多著名的數學家對此問題都做過研究.

歷史上通過對這些經典錯位排列問題的研究，引入了組合數學中的容斥原理和遞推法，使它們成為解決現代諸多數學問題中最基本的工具和方法.

責任編校徐國堅