兒子學奧競。在過春節(jié)期間，重新學習了下高中的排列組合，以便與兒子能溝通。以下是學習筆記。
一、計數(shù)原理基礎(chǔ)概念
- 分類加法原理：完成一件事有兩類不同方案，在第1種方案中有m種不同的方法，在第2種方案中有n種不同的方法，那么完成這件事共有
種不同的方法。要點在2種方案中的方法互不相同。
問題：如果2個方案中方法有相同項呢？ - 分步乘法原理：完成一件事需要兩個步驟，做第1步有m種不同的方法，做第2步有n種不同的方法，那么完成這件事有
種不同的方法。要點是2步中的方法互不影響。
問題：如果兩步中方法相互影響呢？ - 排列：從n個不同元素中取出m（m<=n）個元素，按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列。排列公式為：
。
- 組合：從n個不同元素中取出m（m<=n）個元素合成一組，叫做從n個不同元素中取出m個元素的一個組合。組合公式為：
。
- +分組：把n個相同元素中分成m組（m<=n），共有
分法。
- +分配：把n個不同元素分配給n個不同的對象，共有
分法，與全排列思路相似。
（注）：
1. 排列與組合實際上是分步乘法原理的兩種應(yīng)用而已。
2. 而組合的本質(zhì)只是選取不進行排列。
3. 排列的本質(zhì)是選取加上全排列。
+4. 分組是多次選取的結(jié)果。
+5. 排列的結(jié)果是數(shù)列，而組合的結(jié)果是集合，而分組的結(jié)果是多個集合。
+6. 分配的本質(zhì)是分組加上全排列。 分配是現(xiàn)實世界的要求與規(guī)則。
二、乘法在排列與組合中的意義的不同
舉個例子：
有什么意義？是排列還是組合？
這個問題重要嗎？
這個很重要，如果不知道當前式子是排列還是組合，就無法進行正確計算。
排列的結(jié)果是數(shù)列，而組合的結(jié)果是集合。
上面式子的可以有兩種意義：
- 第一種：從五個人選出兩人當正副班長，選法幾何？
。這明顯是一個排列問題。因為選出后按正副班長這個排列順序，如果是選出兩個人打掃衛(wèi)生，結(jié)果就變成
了。
- 第二種：從5個男生與4個女生中，分別選出一個人去參加乒乓雙打。
大多數(shù)情況下：
三、從元素的相異性來看計數(shù)
（一）無重復(fù)元素（不同元素集合，我們主要學的）
- 元素模型常見有：同學、甲乙丙丁、球隊、課程等。
- 排列應(yīng)用：
，從n個不同元素中選取m個元素的排列。
- 全排列應(yīng)用：
，從n個不同元素中選取n個元素的排列，或?qū)個不同元素直接排列
- 圓排列應(yīng)用：
，n個不同元素圍成一個圓的全排列。
- 項鏈排列應(yīng)用：
，n個不同珠子串成一個項鏈的全排列。
- 組合應(yīng)用：
，從n個不同元素中選擇m個元素的組合。
- 全組合應(yīng)用：
，從n個不同元素中任何選取的組合。
例：壹圓、貳圓、伍圓、拾圓各一張，一共可組成多少幣值（至少取一張）？
答：
- 分組排列：
（n=n1+n2+...+nk，將n個不同元素分成k個按一順序排列的組）
例：將10個人分別分成1人組、2人組、3人組、4人組，共有分法？
答：
-
平均分組排列：
（n=m*k 將n個不同元素平均分成k個按一順序排列的組，每組m個元素）
例：將6個同學分成3組分別命名為1號組,2號組,3號組，然后去打雙打比賽，有幾種分法？
答：
析：不同元素的平均分組排列，也是分配。
-
平均分組組合：
（n=m*k 將n個不同元素平均分成k個組，每組m個元素）
例：將6個同學分成3組，去打雙打比賽，有幾種分法？
答：
-
分組組合：
（n=n1+n2+...+nk，將n個不同元素分成k個組）
例1：4個同學分成3個組去玩游戲，有幾種分法？
答：
析：第一個是有一組是2人，第二個
注：???表示情況比較復(fù)雜，需要具體應(yīng)對。往往這地方也是可以拓展的知識邊界。
-
+分配問題：？？？，（n個不同元素全部分配給m個不同對象時，n>m）
例1：n+1個不同禮物，全部發(fā)給n個同學，每人至少一件，則發(fā)放方法數(shù)為 ____
答：。先將n+1個元素分成n組，然后將不同的n組派發(fā)給n個同學。
答：。通過先n+1個元素分成無序組，再進行分配。
例2：10個不同禮物，全部發(fā)放給四個同學，每個同學最少2件，最多3件，有多少發(fā)放法？
答：
（二）無限重復(fù)元素（可重復(fù)元素，擴展，人的直覺不能識別的元素）
- 元素常見模型有：銀行中的紙幣、數(shù)字、乒乓球、不同顏色的球、顏色
- 排列：
（從n種可重復(fù)元素中選出m個元素的排列）
例：用0、1、2、3四個數(shù)字，能構(gòu)成多少個3位數(shù)（可有重復(fù)數(shù)字）？
答：或
，首位不能為0，故先取首位。
- 組合：
（從n種可重復(fù)元素中選出m的組合）
例：在銀行中從五角、一元、二元、五元、十元、五十元、一百元7種紙幣中任取10張，有多少種組合方式？
答：
（三）有限重復(fù)元素（擴展）
- 元素常見模型舉例：紅藍白球各10個、36的質(zhì)因數(shù)（2個數(shù)字2, 3個數(shù)字3）
- 排列：？？？
注：目前沒有發(fā)現(xiàn)這方面的發(fā)現(xiàn)與研究。
- 組合：？？？（n=n1+n2+...+nk，分別有k種不同元素，每種元素有n1,n2,...,nk個，從所有元素中取出m個元素的組合，其中
）
例：紅、黑、白球各10個，取出16個球，有多少取法？
答：
析：當m>n/2時，可轉(zhuǎn)化成n-m; 當m<max(n1,n2,...,nk)，比m大的顏色，對于m來說是無限取法，也需要調(diào)到m。
注1：對做法有疑問者可以留言，仔細詢問。這里通用作法是分類討論。
注2：???表示情況比較復(fù)雜，需要具體應(yīng)對。往往這地方也是可以拓展研究的知識邊界。
- 全排列：
例：紅旗2面，藍旗3面，白旗4面，在桿上進行排列，可排列出多少標志？
答：
- 全組合：
（其中n1個元素1，n2個元素2，nk個元素k，任意兩元素的組合結(jié)果都不同，有多少組合方法？）
例：，問x,y有多少組正整數(shù)解？
答：
析：，因為3與2皆為質(zhì)數(shù)，故滿足任何兩元素的乘積結(jié)果都不同。
（四）無差異元素（相同元素集合，擴展）
- 元素常見模型：相同的球、幾何圖形或幾何體的頂點、邊長等。無差異元素的排列與組合沒有意義。
- 全組合：
（n個相同的元素，隨意取出，共有多少取法？）
- 析：取出個固定數(shù)量的組合沒有意義
- 分組排列：
例：七個相同的球分給5個班，每個班至少有一個，如何分？
答：
- 分組排列：
（將n個相同元素分成m個可空組的排列）
例：10個完全相同的球分給甲乙丙丁4人，可以有人沒有球，但球必須發(fā)完，有多少分法？
答：
析：無差別元素的分組排列，其實就是無差別元素的分配。
- 分組組合：??? （將n個相同元素分成m個組）
例：不定方程x1+x2+x3=200, x1,x2,x3皆為正整數(shù),且均不相等,且保證x1<x2<x3，問有x1,x2,x3多少組解？
答：
析：為所有x1,x2,x3的解，為總集合；而
是其中有兩數(shù)相等的情況；6是
，指當3數(shù)皆不相等時的所有排列。
注：???表示情況比較復(fù)雜，需要具體應(yīng)對。往往這地方也是可以拓展研究的知識邊界。
四、總結(jié)
- 排列組合比較容易出錯，往往無法檢驗。最好的檢驗辦法是用多種思路，得到同一結(jié)果。
- 對于復(fù)雜的排列組合解題，最好的辦法從小規(guī)模的數(shù)去演繹算法。
- 排列組合最容易出錯的原因是漏算與重復(fù)算。
- 排列組合主要應(yīng)用場景有：排列、組合、分組、+分配、集合、不定方程、質(zhì)因數(shù)、約數(shù)和等。
- 排列組合的本質(zhì)是現(xiàn)實世界事物與時間空間的對應(yīng)與分配問題。
n 個不同元素到m個不同位置的對應(yīng)問題。
(1) 如果n=1，就是組合；
(2) 如果n>m，要求1個位置放1個元素，就是排列；
+(3) 如果n=m，要求1個位置放1個元素，就是全排列，或者是直接分配；
+(4) 如果n>m，要求必須分配完，每個位置必須有，就是分配問題； - 排列組合的本質(zhì)是集合與數(shù)列的轉(zhuǎn)換問題。
(1)排列的過程，是集合向數(shù)列的轉(zhuǎn)換。排列的對象是集合，而結(jié)果是數(shù)列。
(2)組合的過程，是集合向集合的轉(zhuǎn)換。組合的對象是集合，而結(jié)果也是集合。
+(3)分組的對象是集合，而結(jié)果可以是數(shù)列，也可以是集合，視情況而定。
+(4)分配的過程，是集合向集合的分配，分配的對象集合，分配的目標也是集合。
+(5)分組排列的過程 ，是集合先轉(zhuǎn)成大集合，大集合又向數(shù)列的轉(zhuǎn)換
+(6)分組組合的過程 ，是集合向大集合的轉(zhuǎn)換。
