兒子學(xué)奧競昧港。在過春節(jié)期間，重新學(xué)習了下高中的排列組合逻住，以便與兒子能溝通钟哥。以下是學(xué)習筆記。
一瞎访、計數(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ù)元素（不同元素集合，我們主要學(xué)的）
- 元素模型常見有：同學(xué)恢准、甲乙丙丁魂挂、球隊、課程等馁筐。
- 排列應(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個同學(xué)分成3組分別命名為1號組,2號組,3號組笆怠，然后去打雙打比賽，有幾種分法誊爹？
答：
析：不同元素的平均分組排列，也是分配。
-
平均分組組合：
（n=m*k 將n個不同元素平均分成k個組橱乱，每組m個元素）
例：將6個同學(xué)分成3組俱病，去打雙打比賽，有幾種分法搂漠？
答：
-
分組組合：
（n=n1+n2+...+nk迂卢，將n個不同元素分成k個組）
例1：4個同學(xué)分成3個組去玩游戲，有幾種分法桐汤？
答：
析：第一個是有一組是2人冷守，第二個
注：???表示情況比較復(fù)雜拍摇，需要具體應(yīng)對。往往這地方也是可以拓展的知識邊界馆截。
-
+分配問題：充活？？蜡娶？混卵，（n個不同元素全部分配給m個不同對象時，n>m）
例1：n+1個不同禮物窖张，全部發(fā)給n個同學(xué)幕随，每人至少一件，則發(fā)放方法數(shù)為 ____
答：宿接。先將n+1個元素分成n組赘淮，然后將不同的n組派發(fā)給n個同學(xué)。
答：睦霎。通過先n+1個元素分成無序組梢卸，再進行分配。
例2：10個不同禮物副女，全部發(fā)放給四個同學(xué)蛤高，每個同學(xué)最少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)換格嗅。
