排列組合[組合數學中的一種]:排列組合是組合學最基本的概念。所謂排列，就 -百科知識中文網

發展歷程

雖然數學始於結繩計數的遠古時代，由於那時社會的生產水平的發展尚處於低級階段，談不上有什麼技巧。隨著人們對於數的了解和研究，在形成與數密切相關的數學分支的過程中，如數論、代數、函式論以至泛函的形成與發展，逐步地從數的多樣性發現數數的多樣性，產生了各種數數的技巧。

同時，人們對數有了深入的了解和研究，在形成與形密切相關的各種數學分支的過程中，如幾何學、拓撲學以至範疇論的形成與發展，逐步地從形的多樣性也發現了數形的多樣性，產生了各種數形的技巧。近代的集合論、數理邏輯等反映了潛在的數與形之間的結合。而現代的代數拓撲和代數幾何等則將數與形密切地聯繫在一起了。這些，對於以數的技巧為中心課題的近代組合學的形成與發展都產生了而且還將會繼續產生深刻的影響。

由此觀之，組合學與其他數學分支有著必然的密切聯繫。它的一些研究內容與方法來自各個分支也套用於各個分支。當然，組合學與其他數學分支一樣也有其獨特的研究問題與方法，它源於人們對於客觀世界中存在的數與形及其關係的發現和認識。例如，中國古代的《易經》中用十個天干和十二個地支以六十為周期來記載月和年，以及在洛書河圖中關於幻方的記載，是人們至今所了解的最早發現的組合問題甚或是 架構語境學。

於11和12世紀間，賈憲就發現了二項式係數，楊輝將它整理記載在他的《續古抉奇法》一書中。這就是中國通常稱的楊輝三角。事實上，於12世紀印度的婆什迦羅第二也發現了這種組合數。13世紀波斯的哲學家曾講授過此類三角。而在西方，布萊士·帕斯卡發現這個三角形是在17世紀中期。這個三角形在其他數學分支的套用也是屢見不鮮的。同時，帕斯卡和費馬均發現了許多與機率論有關的經典組合學的結果。因此，西方人認為組合學開始於17世紀。組合學一詞是德國數學家萊布尼茨在數學的意義下首次套用。也許，在那時他已經預感到了其將來的蓬勃發展。然而只有到了18世紀歐拉所處時代，組合學才可以說開始了作為一門科學的發展，因為那時，他解決了柯尼斯堡七橋問題，發現了多面體（首先是凸多面體，即平面圖的情形）的頂點數、邊數和面數之間的簡單關係，被人們稱為歐拉公式。甚至，當今人們所稱的哈密頓圈的首創者也應該是歐拉。這些不但使歐拉成為組合學的一個重要組成部分——圖論而且也成為占據現代數學舞台中心的拓撲學發展的先驅。同時，他對導致當今組合學中的另一個重要組成部分——組合設計中的拉丁方的研究所提出的猜想，人們稱為歐拉猜想，直到1959年才得到完全的解決。

於19世紀初，高斯提出的組合係數，今稱高斯係數，在經典組合學中也占有重要地位。同時，他還研究過平面上的閉曲線的相交問題，由此所提出的猜想稱為高斯猜想，它直到20世紀才得到解決。這個問題不僅貢獻於拓撲學，而且也貢獻於組合學中圖論的發展。同在19世紀，由喬治·布爾發現且被當今人們稱為布爾代數的分支已經成為組合學中序理論的基石。當然，在這一時期，人們還研究其他許多組合問題，它們中的大多數是娛樂性的。

20世紀初期，龐加萊聯繫多面體問題發展了組合學的概念與方法，導致了近代拓撲學從組合拓撲學到代數拓撲學的發展。於20世紀的中、後期，組合學發展之迅速也許是人們意想不到的。首先，於1920年費希爾（Fisher，R.A.）和耶茨（Yates，F.）發展了實驗設計的統計理論，其結果導致後來的資訊理論，特別是編碼理論的形成與發展.於1939年，坎托羅維奇（Канторович，Л.В.）發現了線性規劃問題並提出解乘數法。於1947年丹齊克（Dantzig，G.B.）給出了一般的線性規劃模型和理論，他所創立的單純形方法奠定了這一理論的基礎，闡明了其解集的組合結構。直到今天它仍然是套用得最廣泛的數學方法之一。這些又導致以網路流為代表的運籌學中的一系列問題的形成與發展。開拓了人們目前稱為組合最最佳化的一個組合學的新分支。在20世紀50年代，中國也發現並解決了一類稱為運輸問題的線性規劃的圖上作業法，它與一般的網路流理論確有異曲同工之妙。在此基礎上又出現了國際上通稱的中國郵遞員問題。

另一方面，自1940年以來，生於英國的塔特（Tutte，W.T.）在解決拼方問題中取得了一系列有關圖論的結果，這些不僅開闢了現今圖論發展的許多新研究領域，而且對於20世紀30年代，惠特尼（Whitney，H.）提出的擬陣論以及人們稱之為組合幾何的發展都起到了核心的推動作用。應該特別提到的是在這一時期，隨著電子技術和計算機科學的發展愈來愈顯示出組合學的潛在力量。同時，也為組合學的發展提出了許多新的研究課題。例如，以大規模和超大規模積體電路設計為中心的計算機輔助設計提出了層出不窮的問題。其中一些問題的研究與發展正在形成一種新的幾何，人們稱之為組合計算幾何。關於算法複雜性的究，自1971年庫克（Cook，S.A.）提出NP完全性理論以來，已經將這一思想滲透到組合學的各個分支以至數學和計算機科學中的一些分支。

近20年來，用組合學中的方法已經解決了一些即使在整個數學領域也是具有挑戰性的難題。例如，范·德·瓦爾登（Van der Waerden，B.L.）於1926年提出的關於雙隨機矩陣積和式猜想的證明；希伍德（Heawood，P.J.）於1890年提出的曲面地圖著色猜想的解決;著名的四色定理的計算機驗證和扭結問題的新組合不變數發現等。在數學中已經或正在形成著諸如組合拓撲、組合幾何、組合數論、組合矩陣論、組合群論等與組合學密切相關的交叉學科。此外，組合學也正在滲透到其他自然科學以及社會科學的各個方面，例如，物理學、力學、化學、生物學、遺傳學、心理學以及經濟學、管理學甚至政治學等。

根據組合學研究與發展的現狀，它可以分為如下五個分支：經典組合學、組合設計、組合序、圖與超圖和組合多面形與最最佳化.由於組合學所涉及的範圍觸及到幾乎所有數學分支，也許和數學本身一樣不大可能建立一種統一的理論.然而，如何在上述的五個分支的基礎上建立一些統一的理論，或者從組合學中獨立出來形成數學的一些新分支將是對21世紀數學家們提出的一個新的挑戰。
在中國當代的數學家中，較早地在組合學中的不同方面作出過貢獻的有華羅庚、吳文俊、柯召、萬哲先、張里千和陸家羲等.其中，萬哲先和他領導的研究組在有限幾何方面的系統工作不僅對於組合設計而且對於圖的對稱性的研究都有影響.陸家羲的有關不交斯坦納三元系大集的一系列的文章不僅解決了組合設計方面的一個難題，而且他所創立的方法對於其後的研究者也產生了和正產生著積極的作用。

1772年，法國數學家范德蒙德（Vandermonde， A. - T.）以[n]p表示由n個不同的元素中每次取p個的排列數。

瑞士數學家歐拉（Euler， L.）則於1771年以及於1778年以表示由n個不同元素中每次取出p個元素的組合數。

1830年，英國數學家皮科克（Peacock， G）引入符號Cr表示n個元素中每次取r個的組合數。

1869年或稍早些，劍橋的古德文以符號nPr 表示由n個元素中每次取r個元素的排列數，這用法亦延用至今。按此法，nPn便相當於n！。

1872年，德國數學家埃汀肖森（Ettingshausen，B. A. von）引入了符號（np）來表示同樣的意義，這組合符號（Signs of Combinations）一直沿用至今。

1880年，鮑茨（Potts ， R.）以nCr及nPr分別表示由n個元素取出r個的組合數與排列數。

1886年，惠特渥斯（Whit-worth， A. W.）用Cnr和Pnr表示同樣的意義，他還用Rnr表示可重複的組合數。

1899年，英國數學家、物理學家克里斯托爾（Chrystal，G.）以nPr，nCr分別表示由n個不同元素中每次取出r個不重複之元素的排列數與組合數，並以nHr表示相同意義下之可重複的排列數，這三種符號也通用至今。

1904年，德國數學家內托（Netto， E.）為一本百科辭典所寫的辭條中，以Arn表示上述nPr之意，以Crn表示上述nCr之意，後者亦也用符號（n r）表示。這些符號也一直用到現代。

此外，在八卦中，亦運用到了排列組合。

定義及相關

定義及公式

排列的定義：從n個不同元素中，任取m(m≤n,m與n均為自然數,下同）個元素按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列；從n個不同元素中取出m(m≤n）個元素的所有排列的個數，叫做從n個不同元素中取出m個元素的排列數，用符號 A(n,m）表示。

計算公式：

此外 規定0!=1(n!表示n(n-1)(n-2)...1,也就是6！=6x5x4x3x2x1

組合的定義：從n個不同元素中，任取m(m≤n）個元素並成一組，叫做從n個不同元素中取出m個元素的一個組合；從n個不同元素中取出m(m≤n）個元素的所有組合的個數，叫做從n個不同元素中取出m個元素的組合數。用符號 C(n,m) 表示。

計算公式：；C(n,m)=C(n,n-m）。（n≥m)

其他排列與組合公式從n個元素中取出m個元素的循環排列數=A(n,m)/m=n!/m(n-m)!. n個元素被分成k類，每類的個數分別是n1,n2,...nk這n個元素的全排列數為 n!/(n1！×n2！×...×nk!). k類元素，每類的個數無限，從中取出m個元素的組合數為C(m+k-1,m）。

符號

C-Combination 組合數

A-Arrangement 排列數（在舊教材為P-Permutation）

N-Number 元素的總個數

M- 參與選擇的元素個數

！- Factorial階乘

基本計數原理

⑴加法原理和分類計數法

⒈加法原理：做一件事，完成它可以有n類辦法，在第一類辦法中有m1種不同的方法，在第二類辦法中有m2種不同的方法，……，在第n類辦法中有mn種不同的方法，那么完成這件事共有N=m1+m2+m3+…+mn種不同方法。

⒉第一類辦法的方法屬於集合A1，第二類辦法的方法屬於集合A2，……，第n類辦法的方法屬於集合An，那么完成這件事的方法屬於集合A1UA2U…UAn。

⒊分類的要求：每一類中的每一種方法都可以獨立地完成此任務；兩類不同辦法中的具體方法，互不相同（即分類不重）；完成此任務的任何一種方法，都屬於某一類（即分類不漏）。

⑵乘法原理和分步計數法

⒈ 乘法原理：做一件事，完成它需要分成n個步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，……，做第n步有mn種不同的方法，那么完成這件事共有N=m1×m2×m3×…×mn種不同的方法。

⒉合理分步的要求

任何一步的一種方法都不能完成此任務，必須且只須連續完成這n步才能完成此任務；各步計數相互獨立；只要有一步中所採取的方法不同，則對應的完成此事的方法也不同。

3.與後來的離散型隨機變數也有密切相關。

二項式定理

通項公式：a_(i+1)=C(in)a^(n-i)b^i

二項式係數：C(in)楊輝三角：右圖。兩端是1，除1外的每個數是肩上兩數之和。

係數性質：

⑴和首末兩端等距離的係數相等；

⑵當二項式指數n是奇數時，中間兩項最大且相等；

⑶當二項式指數n是偶數時，中間一項最大；

⑷二項式展開式中奇數項和偶數項總和相同，都是2^(n-1）；

⑸二項式展開式中所有係數總和是2^n

組合數的奇偶

奇偶定義：對組合數C(n,k)(n>=k）：將n,k分別化為二進制，若某二進制位對應的n為0，而k為1 ，則C(n,k）為偶數；否則為奇數。

下面是判定方法：

結論：

對於C(n,k），若n&k == k 則c(n,k）為奇數，否則為偶數。

證明：

對於C(n,k），若n&k == k 則c(n,k）為奇數，否則為偶數。

證明：

利用數學歸納法：

由C(n,k) = C(n-1,k) + C(n-1,k-1）；

對應於楊輝三角：

1 1

1 2 1

1 3 3 1

1 4 6 4 1

………………

可以驗證前面幾層及k = 0時滿足結論，下面證明在C(n-1,k）和C(n-1,k-1) (k > 0) 滿足結論的情況下，

C(n,k）滿足結論。

1）.假設C(n-1,k）和C(n-1,k-1）為奇數：

則有：（n-1）&k == k;

（n-1）&(k-1） == k-1;

由於k和k-1的最後一位（在這裡的位指的是二進制的位，下同）必然是不同的，所以n-1的最後一位必然是1

。

現假設n&k == k。

則同樣因為n-1和n的最後一位不同推出k的最後一位是1。

因為n-1的最後一位是1，則n的最後一位是0，所以n&k != k，與假設矛盾。

所以得n&k != k。

2）.假設C(n-1,k）和C(n-1,k-1）為偶數：

則有：（n-1）&k != k;

（n-1）&(k-1） != k-1;

現假設n&k == k.

則對於k最後一位為1的情況：

此時n最後一位也為1，所以有（n-1）&(k-1） == k-1，與假設矛盾。

而對於k最後一位為0的情況：

則k的末尾必有一部分形如：10; 代表任意個0。

相應的，n對應的部分為：1{*}*; *代表0或1。

而若n對應的{*}*中只要有一個為1，則（n-1）&k == k成立，所以n對應部分也應該是10。

則相應的，k-1和n-1的末尾部分均為01，所以（n-1）&(k-1） == k-1 成立，與假設矛盾。

所以得n&k != k。

由1）和2）得出當C(n,k）是偶數時，n&k != k。

3）.假設C(n-1,k）為奇數而C(n-1,k-1）為偶數：

則有：（n-1）&k == k;

（n-1）&(k-1） != k-1;

顯然，k的最後一位只能是0，否則由（n-1）&k == k即可推出（n-1）&(k-1） == k-1。

所以k的末尾必有一部分形如：10;

相應的，n-1的對應部分為：1{*}*;

相應的，k-1的對應部分為：01;

則若要使得（n-1）&(k-1） != k-1 則要求n-1對應的{*}*中至少有一個是0.

所以n的對應部分也就為：1{*}*; （不會因為進位變1為0)

所以 n&k = k。

4）.假設C(n-1,k）為偶數而C(n-1,k-1）為奇數：

則有：（n-1）&k != k;

（n-1）&(k-1） == k-1;

分兩種情況：

當k-1的最後一位為0時：

則k-1的末尾必有一部分形如：10;

相應的，k的對應部分為 : 11;

相應的，n-1的對應部分為 : 1{*}0; （若為1{*}1，則（n-1）&k == k)

相應的，n的對應部分為 : 1{*}1;

所以n&k = k。

當k-1的最後一位為1時：

則k-1的末尾必有一部分形如：01; （前面的0可以是附加上去的）

相應的，k的對應部分為 : 10;

相應的，n-1的對應部分為 : 01; （若為11，則（n-1）&k == k)

相應的，n的對應部分為 : 10;

所以n&k = k。

由3），4）得出當C(n,k）為奇數時，n&k = k。

綜上，結論得證。

著名問題

•計算一些物品在特定條件下分組的方法數目。這些是關於排列、組合和整數分拆的。

•地圖著色問題：對世界地圖著色，每一個國家使用一種顏色。如果要求相鄰國家的顏色相異，是否總共只需四種顏色？這是圖論的問題。

•船夫過河問題：船夫要把一匹狼、一隻羊和一棵白菜運過河。只要船夫不在場，羊就會吃白菜、狼就會吃羊。船夫的船每次只能運送一種東西。怎樣把所有東西都運過河？這是線性規劃的問題。

•中國郵差問題：由中國組合數學家管梅谷教授提出。郵遞員要穿過城市的每一條路至少一次，怎樣行走走過的路程最短？這不是一個NP完全問題，存在多項式複雜度算法：先求出度為奇數的點，用匹配算法算出這些點間的連線方式，然後再用歐拉路徑算法求解。這也是圖論的問題。

•任務分配問題（也稱婚配問題）：有一些員工要完成一些任務。各個員工完成不同任務所花費的時間都不同。每個員工只分配一項任務。每項任務只被分配給一個員工。怎樣分配員工與任務以使所花費的時間最少？這是線性規劃的問題。

•如何構作幻方。

•大樂透

例題分析

難點

⑴從千差萬別的實際問題中抽象出幾種特定的數學模型，需要較強的抽象思維能力；

⑵限制條件有時比較隱晦，需要我們對問題中的關鍵性詞（特別是邏輯關聯詞和量詞）準確理解；

⑶計算手段簡單，與舊知識聯繫少，但選擇正確合理的計算方案時需要的思維量較大；

⑷計算方案是否正確，往往不可用直觀方法來檢驗，要求我們搞清概念、原理，並具有較強的分析能力。

例題

【例1】 從1、2、3、……、20這二十個數中任取三個不同的數組成等差數列，這樣的不同等差數列有多少個？

分析：首先要把複雜的生活背景或其它數學背景轉化為一個明確的排列組合問題。

設a,b,c成等差，∴ 2b=a+c，可知b由a,c決定，

又∵ 2b是偶數，∴ a,c同奇或同偶，即：分別從1，3，5，……，19或2，4，6，8，……，20這十個數中選出兩個數進行排列，由此就可確定等差數列，A（10,2）*2=90*2，因而本題為180。

【例2】 某城市有4條東西街道和6條南北的街道，街道之間的間距相同，若規定只能向東或向北兩個方向沿圖中路線前進，則從M到N有多少種不同的走法?

分析：對實際背景的分析可以逐層深入：

（一）從M到N必須向上走三步，向右走五步，共走八步；

（二）每一步是向上還是向右，決定了不同的走法；

（三）事實上，當把向上的步驟決定後，剩下的步驟只能向右；

從而，任務可敘述為：從八個步驟中選出哪三步是向上走，就可以確定走法數。

∴ 本題答案為：C（8,3）=56。

分析

分析是分類還是分步，是排列還是組合

注意加法原理與乘法原理的特點，分析是分類還是分步，是排列還是組合。

【例3】在一塊並排的10壟田地中，選擇二壟分別種植A，B兩種作物，每種種植一壟，為有利於作物生長，要求A，B兩種作物的間隔不少於6壟，不同的選法共有多少種？

分析：條件中“要求A、B兩種作物的間隔不少於6壟”這個條件不容易用一個包含排列數，組合數的式子表示，因而採取分類的方法。

第一類：A在第一壟，B有3種選擇；

第二類：A在第二壟，B有2種選擇；

第三類：A在第三壟，B有1種選擇，

同理A、B位置互換，共12種。

【例4】從6雙不同顏色的手套中任取4隻，其中恰好有一雙同色的取法有多少種？

（A)240 (B)180 (C)120 (D)60

分析：顯然本題應分步解決。

（一）從6雙中選出一雙同色的手套，有6種方法；

（二）從剩下的十隻手套中任選一隻，有10種方法。

（三）從除前所涉及的兩雙手套之外的八隻手套中任選一隻，有8種方法；

（四）由於選取與順序無關，因（二）（三）中的選法重複一次，因而共240種。

或分步

⑴從6雙中選出一雙同色的手套，有C（6,1）=6種方法

⑵從剩下的5雙手套中任選兩雙，有C（5,2）=10種方法

⑶從兩雙中手套中分別各拿一隻手套，有C（2,1）×C（2,1）=4種方法。

同樣得出共⑴×⑵×⑶=240種。

【例5】．身高互不相同的6個人排成2橫行3縱列，在第一行的每一個人都比他同列的身後的人個子矮，則所有不同的排法種數為_______。

分析：每一縱列中的兩人只要選定，則他們只有一種站位方法，因而每一縱列的排隊方法只與人的選法有關係，共有三縱列，從而有C（6,2）×C（4,2）×C（2,2）=90種。

【例6】在11名工人中，有5人只能當鉗工，4人只能當車工，另外2人能當鉗工也能當車工。現從11人中選出4人當鉗工，4人當車工，問共有多少種不同的選法?

分析：採用加法原理首先要做到分類不重不漏，如何做到這一點？分類的標準必須前後統一。

以兩個全能的工人為分類的對象，考慮以他們當中有幾個去當鉗工為分類標準。

第一類：這兩個人都去當鉗工，C（2,2）×C（5,2）×C（4,4）=10種；

第二類：這兩個人都去當車工，C（5,4）×C（2,2）×C（4,2）=30種；

第三類：這兩人既不去當鉗工，也不去當車工C（5,4）×C（4,4）=5種。

第四類：這兩個人一個去當鉗工、一個去當車工，C（2,1）×C（5,3）×C（4,3）=80種；

第五類：這兩個人一個去當鉗工、另一個不去當車工，C（2,1）×C（5,3）×C（4,4）=20種；

第六類：這兩個人一個去當車工、另一個不去當鉗工，C（5,4）×C（2,1）×C（4,3）=40種；

因而共有185種。

【例7】現有印著0，1，3，5，7，9的六張卡片，如果允許9可以作6用，那么從中任意抽出三張可以組成多少個不同的三位數?

分析：有同學認為只要把0，1，3，5，7，9的排法數乘以2即為所求，但實際上抽出的三個數中有9的話才可能用6替換，因而必須分類。

抽出的三數含0，含9，有32種方法；

抽出的三數含0不含9，有24種方法；

抽出的三數含9不含0，有72種方法；

抽出的三數不含9也不含0，有24種方法。

因此共有32+24+72+24=152種方法。

【例8】停車場劃一排12個停車位置，今有8輛車需要停放，要求空車位連在一起，不同的停車方法有多少種?

分析：把空車位看成一個元素，和8輛車共九個元素排列，因而共有A（9,9）=362880種停車方法。

特殊優先

特殊元素，優先處理；特殊位置，優先考慮。

【例9】六人站成一排，求

⑴甲、乙既不在排頭也不在排尾的排法數

⑵甲不在排頭，乙不在排尾，且甲乙不相鄰的排法數

分析：⑴按照先排出首位和末尾再排中間四位分步計數

第一步：排出首位和末尾、因為甲乙不在首位和末尾，那么首位和末尾實在其它四位數選出兩位進行排列、一共有A（4,2）=12種；

第二步：由於六個元素中已經有兩位排在首位和末尾，因此中間四位是把剩下的四位元素進行順序排列，

共A（4,4）=24種；

根據乘法原理得即不再排頭也不在排尾數共12×24=288種。

⑵第一類：甲在排尾，乙在排頭，有A（4,4）種方法。

第二類：甲在排尾，乙不在排頭，有3×A（4,4）種方法。

第三類：乙在排頭，甲不在排尾，有3×A（4,4）種方法。

第四類：甲不在排尾也不在排頭，乙不在排頭也不在排尾，有6×A（4,4）種方法（排除相鄰）。

共A（4,4）+3×A（4,4）+3×A（4,4）+6×A（4,4）=312種。

【例10】對某件產品的6件不同正品和4件不同次品進行一一測試，至區分出所有次品為止。若所有次品恰好在第五次測試時被全部發現，則這樣的測試方法有多少種可能?

分析：本題意指第五次測試的產品一定是次品，並且是最後一個次品，因而第五次測試應算是特殊位置了，分步完成。

第一步：第五次測試的有C（4,1）種可能；

第二步：前四次有一件正品有C（6,1）中可能。

第三步：前四次有A（4,4）種可能。

∴ 共有576種可能。

捆綁與插空

【例11】8人排成一隊

⑴甲乙必須相鄰

⑵甲乙不相鄰

⑶甲乙必須相鄰且與丙不相鄰

⑷甲乙必須相鄰，丙丁必須相鄰

⑸甲乙不相鄰，丙丁不相鄰

分析：⑴甲乙必須相鄰，就是把甲乙捆綁（甲乙可交換）和7人排列A（7,7）×A（2，2）

⑵甲乙不相鄰，A（8,8）-A（7,7）×2。或A（6,6）×A(7,2)

⑶甲乙必須相鄰且與丙不相鄰，先求甲乙必須相鄰且與丙相鄰A（6,6）×2×2

甲乙必須相鄰且與丙不相鄰A（7,7）×2-A（6,6）×2×2

⑷甲乙必須相鄰，丙丁必須相鄰A（6,6）×2×2

⑸甲乙不相鄰，丙丁不相鄰，A（8,8）-A（7,7）×2×2+A（6,6）×2×2

【例12】某人射擊8槍，命中4槍，恰好有三槍連續命中，有多少種不同的情況?

分析：∵ 連續命中的三槍與單獨命中的一槍不能相鄰，因而這是一個插空問題。另外沒有命中的之間沒有區別，不必計數。即在四發空槍之間形成的5個空中選出2個的排列，即A（5,2）。

【例13】 馬路上有編號為l，2，3，……，10 十個路燈，為節約用電又看清路面，可以把其中的三隻燈關掉，但不能同時關掉相鄰的兩隻或三隻，在兩端的燈也不能關掉的情況下，求滿足條件的關燈方法共有多少種?

分析：即關掉的燈不能相鄰，也不能在兩端。又因為燈與燈之間沒有區別，因而問題為在7盞亮著的燈形成的不包含兩端的6個空中選出3個空放置熄滅的燈。∴ 共C（6,3）=20種方法。

方法二：

把其中的3隻燈關掉總情況有C（8，3)種

關掉相鄰的三隻有C（6，1)種

關掉相鄰的兩隻有2*C（7，2)-12種
所以滿足條件的關燈方法有:
C（8，3)-C（6，1)-[2*C（7，2)-12]
=56-6-(42-12)
=20種

間接計數法

⑴排除法

【例14】三行三列共九個點，以這些點為頂點可組成多少個三角形?

分析：有些問題正面求解有一定困難，可以採用間接法。

所求問題的方法數=任意三個點的組合數-共線三點的方法數，

∴ 共76種。

【例15】正方體8個頂點中取出4個，可組成多少個四面體?

分析：所求問題的方法數=任意選四點的組合數-共面四點的方法數，

∴ 共C（8,4）-12=70-12=58個。

【例16】1，2，3，……，9中取出兩個分別作為對數的底數和真數，可組成多少個不同數值的對數?

分析：由於底數不能為1。

⑴當1選上時，1必為真數，∴ 有一種情況。

⑵當不選1時，從2--9中任取兩個分別作為底數，真數，共A（8,2）=56，其中log2為底4=log3為底9，log4為底2=log9為底3,log2為底3=log4為底9,log3為底2=log9為底4.

因而一共有56-4+1=53個。

【例17】 六人排成一排，要求甲在乙的前面，（不一定相鄰），共有多少種不同的方法? 如果要求甲乙丙按從左到右依次排列呢?

分析：（一）實際上，甲在乙的前面和甲在乙的後面兩種情況對稱，具有相同的排法數。因而有A(6，6)/2=360種。

（二）先考慮六人全排列A(6,6)種；其次甲乙丙三人實際上只能按照一種順序站位，因而前面的排法數重複了A(3,3)種， ∴ 有A(6，6)/A(3,3)=120種。

【例18】5男4女排成一排，要求男生必須按從高到矮的順序，共有多少種不同的方法?

分析：（一）首先不考慮男生的站位要求，共A（9,9）種；男生從左至右按從高到矮的順序，只有一種站法，因而上述站法重複了A(5,5)次。因而有A(9,9,)/A(5,5,)=9×8×7×6=3024種

若男生從右至左按從高到矮的順序，只有一種站法，同理也有3024種，綜上，有6048種。

（二）按照插空的方式進行思考。

第一步：4個女生先在9個位置中選擇4個，為A(9,4)種方式；

第二步：男生站剩下的位置，因為必須從高到矮的順序，沒有規定方向，所以有2種；

綜上，總的站法數有A(9,4)×2=6048種。

【例19】 三個相同的紅球和兩個不同的白球排成一行，共有多少種不同的方法?

分析：先認為三個紅球互不相同，共A（5,5）=120種方法。

而由於三個紅球所占位置相同的情況下，共A（3,3）=6變化，因而共A（5,5）/A（3,3）=20種。

公式P是指排列，從N個元素取R個進行排列（即排序）。（P是舊用法，教材上多用A，Arrangement)

公式C是指組合，從N個元素取R個，不進行排列（即不排序）。

擋板的使用

【例20】10個名額分配到八個班，每班至少一個名額，問有多少種不同的分配方法?

分析：把10個名額看成十個元素，在這十個元素之間形成的九個空中，選出七個位置放置檔板，則每一种放置方式就相當於一種分配方式。因而共36種。

區別與聯繫

所有的排列都可以看作是先取組合，再做全排列；同樣，組合如補充一個階段（排序）可轉化為排列問題。

【例21】用數字0，1，2，3，4，5組成沒有重複數字的四位數，

⑴可組成多少個不同的四位數?

⑵可組成多少個不同的四位偶數

⑶可組成多少個能被3整除的四位數?

分析：⑴有A（6,4）-A（5,3）=300個。

⑵分為兩類：0在末位，則有A（5,3）=60種：0不在末位，則有C（2,1）×A（5,3）-C（2,1）×A（4,2）=96種。

∴ 共60+96=156種。

⑶先把四個相加能被3整除的四個數從小到大列舉出來，即先選

0，1，2，3

0，1，3，5

0，2，3，4

0，3，4，5

1，2，4，5

它們排列出來的數一定可以被3整除，再排列，有：4×[A（4,4）-A（3,3）]+A（4,4）=96種。

分組問題

【例22】 5名學生分配到4個不同的科技小組參加活動，每個科技小組至少有一名學生參加，則分配方法共有多少種？

分析：（一）先把5個學生分成二人，一人，一人，一人各一組。

其中涉及到平均分成三組，有C（5,3）=10種分組方法。可以看成4個板三個板不空的隔板法。

（二）再考慮分配到四個不同的科技小組，有A（4,4）=24種，

由（一）（二）可知，共10×24=240種。

幾何問題

【 例23】某區有7條南北向街道，5條東西向街道（如右圖）

⑴圖中共有多少個矩形？

⑵從A點到B點最近的走法有多少種？

分析：⑴在7條豎線中任選2條，5條橫線中任選2條，這樣4條線

可組成1個矩形，故可組成矩形C（7,2）·C（5,2）=210個

⑵每條東西向的街道被分成4段，每條南北向的街道被分成6段，從A到B最短的走法，無論怎樣走，一定包括10段，其中6段方向相同，另外4段方向相同，每種走法，即是從10段中選出6段，這6段是走東西方向的，共有C（10,6）=C（10,4）=210種走法（同樣可以從10段中選出4段走南北方向，每一種選法即是1種走法）。所以共有210種走法。

口訣

排列、組合、二項式定理公式口訣：

加法乘法兩原理，貫穿始終的法則。與序無關是組合，要求有序是排列。

兩個公式兩性質，兩種思想和方法。歸納出排列組合，套用問題須轉化。

排列組合在一起，先選後排是常理。特殊元素和位置，首先注意多考慮。

不重不漏多思考，捆綁插空是技巧。排列組合恆等式，定義證明建模試。

關於二項式定理，中國楊輝三角形。兩條性質兩公式，函式賦值變換式。

排列組合[組合數學中的一種]

基本信息