淺析排列組合中的重復(fù)計算問題

1、例析排列組合中的重復(fù)計算的產(chǎn)生及對策無錫市洛社高級中學(xué)戎鋼學(xué)生在解排列組合的題目時，往往容易出現(xiàn)考慮不周全，漏解的情況。另外有些類型的排列組合題目較容易出現(xiàn)重復(fù)計算的問題，而且此類問題較隱蔽，學(xué)生不容易發(fā)現(xiàn)。在解題時，應(yīng)做到既不重復(fù)遺漏，又能判斷解題的正誤，并能加以剖析。這樣對于學(xué)生解題能力的提高大有好處。一、分步引起的重復(fù)計算例 1:從 4 臺甲型機和 5 臺乙型電視機中任意取出 3 臺，其中至少有甲型和乙型機各 1 臺，則不同的取法有多少種？【錯解】 先保證各 1 臺，在從剩下的機子中任取一臺。即分三步：第一步從甲型機中取一臺，有 C41 種取法；第二步從乙型機中取一臺，有C51 種取法；

2、第三步從剩下的七臺機子中取一臺，有C17 種取法，根據(jù)乘法原理，共有C41C51C71140 種取法?！痉治觥吭O(shè)甲型機種有 a、b 兩臺機子 ，乙型機中有 A 、B 兩臺機子，根據(jù)上述選法，其中有一種取法可以是“先選 a，再選 A ，再選 b”,另外一種取法是“先選 b，再選 A ，再選 a”。而很明顯，上述兩種取法是同一種結(jié)果，出現(xiàn)重復(fù)。究其原因是本題使用的是分類計數(shù)原理（分步原理） 。而分步必然有先有后，也就有順序，跟排列有關(guān)。本題中無論是取兩臺甲型機還是兩臺乙型機，對于這兩臺機而言，只是一個組合，沒有先后，因此重復(fù)了兩遍。【正解】根據(jù)結(jié)果分類，第一類：兩臺甲型機，有C42 C51 種取法

3、；第二類：兩臺乙型機，有 C41 C52 種取法，根據(jù)分類計數(shù)原理，共有C42 C51C41 C5270 種取法。二、涉及到平均分組中的重復(fù)計算例 2: 袋中有紅、白、黃球各一個，每次任取一球，記下顏色后放回，當各種顏色均被取到時結(jié)束，則取球結(jié)束時，一共取了五次的不同取法有多少種？【錯解】由題意，第五次一定是第三種顏色的球。前四次取到其他兩種顏色的球。先分步，第五次有C31 種顏色的可能，再分類討論前四次的情況，第一類：剩下的兩種顏色的球，一種顏色的取到三次，另外一種取到一次。分步完成，先選出一種顏色，被取到三次，有 C21 種可能，然后這種顏色在前四次中被取到有C43 中情況，共有C21C4

4、3 種情況；第二類，類似第一類， 共有 C21 C42 種情況， 由分步原理共有 C31 (C21 C42C21C43 ) 60 種不同的取法?！酒饰觥勘绢}中在分類時涉及到平均分組的問題。在第二類中兩種顏色各取到兩次的情況，計數(shù)重復(fù)。比如假設(shè)第五次取到白色，C21 選取的是紅色，在四次取球中，C42 中前兩次是紅色，后兩次是黃色，即紅紅黃黃白是其中一種情況；若C21 選取的是黃色，在四次取球中，后兩次是黃色，前兩次是黃色，對于該算法來講是不同的兩次，而結(jié)果是相同的，應(yīng)是 C31 (C12 C43C42 )42。【正解】本題可以通過舉例探究，分類討論避開平均分組。不妨假設(shè)最后一次取的是白球（由分

5、步原理應(yīng)是C13 種可能）則前四次應(yīng)只有紅色和黃色?？蛇M一步細分為三類：三紅一黃，兩紅兩黃，一紅三黃，各有C14 、 C42 、 C43 種可能。由等可能性，共有C13 (C14C42C43 )42種可能。平均分組高考沒有明確要求，但06 年江蘇最后一道選擇題卻又涉及到。學(xué)生對平均分組計數(shù)時么除以組數(shù)的全排列難以理解， 解題時也不容易想到。 本題通過特殊化的思想，通過舉例探究，找到相同點，弄清楚其中的關(guān)系，思路相對自然，容易接受和理解。三、分類不清引起的重復(fù)例 3：定義非空集合A 的真子集的真子集為A 的“孫集”，則集合 1 ，3，5，7 的孫集的個數(shù)為 _。【解析】本題源于課本，又高于課本。

6、根據(jù)真子集的定義，學(xué)生不難寫出集合1 ，3，5，7 的真子集，應(yīng)有24 1 15 個，然后在找出每個真子集的真子集即可。由于四元子集的真子集可以分為三類即空集； 一元真子集； 二元真子集； 三元真子集。 空集沒有真子集，一元集合的真子集有 2 個，其中一個為空集； 二元集合的真子集有 3 個，其中一個為空集；三元集合的真子集有 7 個，其中一個為空集。除去空集重復(fù)，一共有C14 1C42 2C43 6141種。上述解法是錯的。仍以舉例分析。 一元真子集如1 或 3 等等，其真子集只能是空集，僅算一個；二元子集如 1,3 或1,5等等，其真子集為空集和一元集合 1,3,5，不難發(fā)現(xiàn)，一元真子集也

7、有重復(fù)，三元集合的真子集也也有類似的重復(fù)。因此上述解法由于分類后并不清楚，仍有重復(fù)計算。正確的解法：由分析不難看出，盡管每種分類都有重復(fù)，但可以發(fā)現(xiàn)，其孫集必為真子集，而且最多是二元真子集。 所以分三類： 空集；一元集合， 有 C41 個；二元集合， 有 C42個，共計 C40C41C4211個。對策： 此類重復(fù)計算問題往往比較隱蔽，學(xué)生易犯錯誤，而且不易察覺。但仔細回顧這三道例題，我們還是有規(guī)律可尋，有方法可依的。一、通過題組訓(xùn)練，強化模式識別。對于易產(chǎn)生重復(fù)的題目有很多還是有相似之處的?？梢酝ㄟ^題組的形式，讓學(xué)生強化對該類題目的辨析和認識。筆者列舉如下一組問題，請讀者仔細考慮。（ 1）袋中

8、裝有大小相同、編號各不相同的五個紅球、四個黑球，從中取出 5 個，紅球，黑球各至少有 2 個的不同取法有多少種？（ 2）某演出隊有 9 名歌舞演員，其中 7 人會表演唱歌節(jié)目， 5 人會表演舞蹈節(jié)目，今從 9 人中選 2 人， 1 人表演唱歌， 1 人表演舞蹈，則不同的選法有多少種？（ 3）有學(xué)生 10 人，其中團員4 人，現(xiàn)平均分成2 組，若每組都要分2 名團員，那么不同的分組方法有多少種？（ 4）某籃球隊有11 名隊員，其中5 人只能打前鋒，4 人只能打后衛(wèi)，其余2 人可打前鋒可打后衛(wèi)。現(xiàn)從中選5 人（ 3 前鋒 2 后衛(wèi)）出場，有幾種選法？現(xiàn)從中選10 人組成 2 個隊對抗，每隊都是3

9、前鋒 2 后衛(wèi)，有幾種選法？（ 5） A 的一邊有4 個點，另一邊有5 個點，連同頂點一共10 個點，可以作出多少個三角形？（ 6）有紅黃藍三種顏色卡片各5 張，每種卡片上分別寫有1，2，3， 4， 5 五個數(shù)字，如果每次提取4 張卡片，要求顏色齊全，數(shù)字不同，那么取法種數(shù)共有多少種？（ 7）從 1，2， 3， 10 這 10 個數(shù)字種有放回地抽取3 次，每次抽取1 個數(shù)字，3次抽取中最小數(shù)為3 的所有可能種數(shù)為多少？（提示： 1、 2 兩題參考例1； 3、 4 兩題參考例2； 5、6、 7 先考慮分組。）二、由小見大，以點帶面，逐步摸清規(guī)律，合理分解。在剖析重復(fù)計算產(chǎn)生的原因的過程當中，我們不難發(fā)現(xiàn)錯誤的想法源于對整體情況的把握不夠完整，問題考慮得不夠清晰。對于這樣的問題，學(xué)生的反映或者是無從下手，或者是惰于思考， 想不周全。 實際上以上三例的解析已經(jīng)給出行之有效的一套方案。一方面，我們通過舉例發(fā)現(xiàn)重復(fù)計算的問題，而另一方面， 我們還是通過舉例，先列舉出一些特例，同時在舉例的過程中，尋找共同點，逐步發(fā)現(xiàn)