不錯-排列組合問題之全錯位排列問題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 排列組合問題之全錯位排列問題 （一個通項公式和兩個遞推關(guān)系）一、問題引入： 問題、名同學(xué)各寫一張賀卡，先集中起來，然后每人從中拿出一張別人寫的賀卡，則四張賀卡的不同分配方式共有多少種？ 問題、將編號為，的四個小球分別放入編號為，的四個盒子中，要求每個盒子放一個小球，且小球的編號與盒子的編號不能相同，則共有多少種不同的放法？ 這兩個問題的本質(zhì)都是每個元素都不在自己編號的位置上的排列問題，我們把這種限制條件的排列問題叫做全錯位排列問題。 問題、五位同學(xué)坐在一排，現(xiàn)讓五位同學(xué)重新坐，至多有兩位同學(xué)坐自己原來的位置，則不同的坐法有多少種？ 解析：可以分類解決：第一類，所有同

2、學(xué)都不坐自己原來的位置； 第二類，恰有一位同學(xué)坐自己原來的位置； 第三類，恰有兩位同學(xué)坐自己原來的位置。 對于第一類，就是全錯位排列問題；對于第二、第三類有部分元素還占有原來的位置，其余元素可以歸結(jié)為全錯位排列問題，我們稱這種排列問題為部分錯位排列問題。 設(shè)個元素全錯位排列的排列數(shù)為，則對于問題，第一類全錯位排列的排列數(shù)為；第二類先確定一個排原來位置的同學(xué)有種可能，其余四個同學(xué)全錯位排列，所以第二類的排列數(shù)為；第三類先確定兩個排原位的同學(xué)，有種可能，其余三個同學(xué)全錯位排列，所以第三類的排列數(shù)為，因此問題的答案為：。由于生活中很多這樣的問題，所以我們有必要探索一下關(guān)于全錯位排列問題的解決方法。2

3、、 全錯位排列數(shù)的遞推關(guān)系式之一： 定義：一般地，設(shè)個編號為、 、的不同元素、，排成一排，且每個元素均不排在與其編號相同的位置，這樣的全錯位排列數(shù)為，則 ；，。 遞推關(guān)系的確立： 顯然當、時，有，。 當時，在個不同元素中任取一個元素不排在與其編號相對應(yīng)的 位，必排在剩下個位置之一，所以有種排法。 對每一種排法，如排在位，對應(yīng)位的元素的排位總有兩種情況： 第一種情況：恰好排在位上。此時，排在位，排在位，元素，排位已定。還剩個元素，每個元素均有一個不能排的位置，它們的排位問題就轉(zhuǎn)化為 個元素全錯位排列數(shù)，應(yīng)有種。第二種情況：不排在位上。此時，仍排在位，不排在位，則有個位置可排。除外，還有個元素，每

4、個元素均有一個不能排的位置，問題就轉(zhuǎn)化為n個元素全錯位排列數(shù)，應(yīng)有種。由乘法原理和加法原理可得：，。利用此遞推關(guān)系可以分別算出，。問題的答案為：。3、 全錯位排列數(shù)的通項公式之一： 探索：規(guī)定，試計算以下各式的值： ； ； 。 很容易計算三式的值依次為，。而這與利用上面的遞推關(guān)系式得到的，剛好吻合。即 ；。 猜想： 根據(jù)上面的探索，我們可以猜想個元素全錯位排列數(shù)為 為了更容易看清其本質(zhì)，我們對這個式子進行變形，得到： 。 證明（數(shù)學(xué)歸納法）： 當，時，式顯然成立。 假設(shè)，時，式成立。 則當時，由上面的遞推關(guān)系式可得： 所以，當時，式也成立。 由以上過程可知個元素全錯位排列的排列數(shù)為： 4、 全錯位排列數(shù)的