不錯(cuò)-排列組合問題之全錯(cuò)位排列問題.doc

《不錯(cuò)-排列組合問題之全錯(cuò)位排列問題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

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

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

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

5、個(gè)元素全錯(cuò)位排列的排列數(shù)為：二、全錯(cuò)位排列數(shù)的遞推關(guān)系式之二：由，，，，可得：；；；于是猜想：證明：由上面已證明的全錯(cuò)位排列數(shù)通項(xiàng)公式可知：右邊左邊所以。