不錯-排列組合問題之全錯位排列問題_第1頁
不錯-排列組合問題之全錯位排列問題_第2頁
不錯-排列組合問題之全錯位排列問題_第3頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論