09公務(wù)員輔導(dǎo)：排列組合問題之錯(cuò)位排列問題

更新時(shí)間：2009-10-19 15:27:29 來源：|0

瀏覽

國(guó)家公務(wù)員報(bào)名、考試、查分時(shí)間免費(fèi)短信提醒

錯(cuò)位排列問題是一個(gè)古老的問題，最先由貝努利（Bernoulli）提出，其通常提法是：n個(gè)有序元素，全部改變其位置的排列數(shù)是多少？所以稱之為“錯(cuò)位”問題。大數(shù)學(xué)家歐拉（Euler）等都有所研究。下面先給出一道錯(cuò)位排列題目，讓考友有直觀感覺。
　　例1．五個(gè)編號(hào)為1、2、3、4、5的小球放進(jìn)5個(gè)編號(hào)為1、2、3、4、5的小盒里面，全錯(cuò)位排列（即1不放1，2不放2，3不放3，4不放4，5不放5，也就是說5個(gè)全部放錯(cuò)）一共有多少種放法？
　　【解析】：直接求5個(gè)小球的全錯(cuò)位排列不容易，我們先從簡(jiǎn)單的開始。
　　小球數(shù)/小盒數(shù) 全錯(cuò)位排列
　　1 0
　　2 1（即2、1）
　　3 2（即3、1、2和2、3、1）
　　4 9
　　5 44
　　6 265
　　當(dāng)小球數(shù)/小盒數(shù)為1~3時(shí)，比較簡(jiǎn)單，而當(dāng)為4~6時(shí)，略顯復(fù)雜，考友只需要記下這幾個(gè)數(shù)字即可（其實(shí)0，1，2，9，44，265是一個(gè)有規(guī)律的數(shù)字推理題，請(qǐng)各位想想是什么？）由上述分析可得，5個(gè)小球的全錯(cuò)位排列為44種。
　　上述是最原始的全錯(cuò)位排列，但在實(shí)際公務(wù)員考題中，會(huì)有一些“變異”。
　　例2．五個(gè)瓶子都貼了標(biāo)簽，其中恰好貼錯(cuò)了三個(gè)，則錯(cuò)的可能情況共有多少種？
　　【解析】：做此類題目時(shí)通常分為兩步：第一步，從五個(gè)瓶子中選出三個(gè)，共有種選法；第二步，將三個(gè)瓶子全部貼錯(cuò)，根據(jù)上表有2種貼法。則恰好貼錯(cuò)三個(gè)瓶子的情況有種。
　　【拓展】：想這樣一個(gè)問題：五個(gè)瓶子中，恰好貼錯(cuò)三個(gè)是不是就是恰好貼對(duì)兩個(gè)呢？答案是肯定的，是。那么能不能這樣考慮呢？第一步，從五個(gè)瓶子中選出二個(gè)瓶子，共有種選法；第二步，將兩個(gè)瓶子全部貼對(duì)，只有1種方法，那么恰好貼對(duì)兩個(gè)瓶子的方法有種。問題出來了，為什么從貼錯(cuò)的角度考慮是20種貼法，而從貼對(duì)的角度考慮是10種貼法呢。在此明確告知，后者的解題過程是錯(cuò)誤的，請(qǐng)考友想想為什么？
　　【王永恒提示】：在處理錯(cuò)位排列問題時(shí)，無論問恰好貼錯(cuò)還是問恰好貼對(duì)，都要從貼錯(cuò)的角度去考慮，這樣處理問題簡(jiǎn)單且不易出錯(cuò)。