想把這門課學明白的人我先把話說在前面《組合數(shù)學與應用》不是一門靠死記硬背能過關的課。它不考你背了多少公式而是考你能不能把一個實際問題“翻譯”成組合模型再用合適的方法把它算出來。我在電子科技大學讀研時選的這門課當時覺得它就是花式數(shù)數(shù)后來做算法、搞數(shù)據(jù)分析、看分布式系統(tǒng)里的哈希和一致性設計才發(fā)現(xiàn)當年學的那些計數(shù)思路全在后邊等著我。這篇東西我按自己的學習路徑和踩坑經(jīng)歷來寫適合正在選課、準備考研復試、或者單純想補組合數(shù)學這塊短板的同學參考。1. 這門課到底在講什么課程定位與知識體系1.1 不只是數(shù)數(shù)組合數(shù)學的核心思維很多第一次接觸組合數(shù)學的人第一反應是這不就是高中學過的排列組合嗎還真不是。高中那點排列組合只能算入門級工具組合數(shù)學的核心是在“有限集合”的框架下回答三類問題存在性、計數(shù)和構造。存在性問“這東西到底有沒有”計數(shù)問“如果有一共有多少種”構造問“能不能給出一套具體的方案”。這三個問題對應的思維方式幾乎貫穿整個計算機科學。判斷一個算法有沒有解是在做存在性分析估算狀態(tài)空間、分析復雜度上界是在做計數(shù)設計一個具體的實例、生成測試數(shù)據(jù)是在做構造。我在實際工作中最深的一個體會是很多人數(shù)據(jù)結構學得很好但一碰到“這個方案可行性的邊界在哪”就想不清楚本質上就是組合數(shù)學那套思維沒建立起來。成電的《組合數(shù)學與應用》這門課正好就是把這套思維系統(tǒng)化地訓練一遍。它不會像數(shù)學分析那樣追求每一步嚴格的極限推導而是更強調(diào)怎么把模型建出來、怎么用現(xiàn)成工具快速得到結果。對計算機專業(yè)的學生來說這門課實際是算法課和離散數(shù)學課的連接器。1.2 成電版課程的知識骨架我根據(jù)當年上課的講義和考試大綱把整門課的骨架做了個梳理核心模塊大概有這幾塊模塊核心內(nèi)容在算法/工程中的應用計數(shù)基礎排列、組合、加法原理、乘法原理、二項式系數(shù)狀態(tài)數(shù)估算、算法復雜度下界分析容斥原理包含-排除公式、錯排、歐拉函數(shù)概率論、數(shù)論算法、清洗數(shù)據(jù)時的去重邏輯鴿巢原理抽屜原理、平均值原理、Ramsey數(shù)哈希沖突必然性論證、圖論證明遞推關系常系數(shù)線性遞推、特征方程、Catalan數(shù)動態(tài)規(guī)劃、時間序列模型、算法復雜度遞推求解生成函數(shù)普通生成函數(shù)、指數(shù)型生成函數(shù)、形式冪級數(shù)組合恒等式證明、概率母函數(shù)、隨機過程波利亞計數(shù)Burnside引理、Polya定理對稱性去重、化學同分異構體計數(shù)、循環(huán)節(jié)分析組合設計拉丁方、有限射影平面、正交表實驗設計、糾錯碼、獨立冗余磁盤陣列這個表不是課程大綱的復讀而是我提醒自己“學這個到底能干嘛”用的。每次覺得某個理論抽象得想放棄時我就對照這個表找一個現(xiàn)實場景一下就有了學下去的動力。2. 核心內(nèi)容拆解五塊硬骨頭的學法與算法2.1 計數(shù)基礎與二項式系數(shù)所有上層建筑的基石排列組合這部分很多人覺得簡單但恰恰是這里最容易埋下隱患。加法原理和乘法原理是整個計數(shù)體系的兩個公理級工具前者處理“分類互斥”的情況后者處理“分步獨立”的情況。什么時候該加、什么時候該乘我當年考試第一道大題就掛在這。一個典型的題目是一個任務要么從A方案中選要么從B方案中選A方案有m種做法B方案有n種做法總共mn種。這看似簡單可一旦混進“先選方案再選具體做法”這種情形該用乘法還是加法就容易亂。我的判別方法只有一句話看這個動作是一步完成還是需要分成多個連續(xù)的子步驟。一步完成的動作做加法分步完成的流程做乘法。二項式系數(shù)這塊重點不在背帕斯卡三角而在幾個恒等式的活用。課堂上學過的C(n,k) C(n-1,k) C(n-1,k-1)是遞推版本C(n,k) n!/(k!(n-k)!)是階乘版本還有一個C(n,k) C(n,n-k)的對稱性。這幾個恒等式考試時能直接省掉大量計算時間。比如算C(50,48)如果先展開50!再約分計算量巨大但用對稱性轉成C(50,2)直接口算出答案是1225。2.2 容斥原理與鴿巢原理從存在性到精確計數(shù)容斥原理的公式大家可能都會背 |A∪B∪C| |A||B||C| - |A∩B| - |A∩C| - |B∩C| |A∩B∩C|。但這個公式在真實題目里的難點不是套公式而是怎么定集合。我當年做錯排問題時就栽過跟頭。錯排問題問的是n個元素做全排列有多少種排列方式讓每個元素都不在自己的原位上。直接枚舉根本不可能容斥的做法是設Ai表示“第i個元素在第i個原位上”的排列集合錯的排列數(shù)總排列數(shù)減去“至少一個元素在原位”的并集大小。這個思路看起來簡單實際操作時很容易漏算交集。Ai∩Aj表示第i個和第j個元素都在原位剩下n-2個元素任意排列所以有(n-2)!種。套容斥公式簡化后就得到著名的錯排公式D(n) n! × (1 - 1/1! 1/2! - 1/3! ... (-1)^n × 1/n!)這個公式我不只是背我建議你也推一遍。推的過程比背十遍更有價值因為容斥法的“交疊抵消”思想在概率論中算并集概率、在算法中做去重統(tǒng)計用的都是同一套邏輯。鴿巢原理看著像廢話用起來卻極有威力。它說的是如果把n1個物體放進n個盒子至少有一個盒子里有2個或以上的物體。可它在證明里的用法常常是先構造盒子再往里面塞東西。證明“任意n1個正整數(shù)中必存在兩個數(shù)之差能被n整除”時做法是按模n的余數(shù)分類n1個數(shù)對應n個余數(shù)類必有至少兩個數(shù)在同一余數(shù)類問題就證完了。2.3 遞推關系與特征方程動態(tài)規(guī)劃的數(shù)學母體遞推關系是組合數(shù)學里和算法關系最緊密的一塊。動態(tài)規(guī)劃的狀態(tài)轉移方程本質上就是遞推關系算法復雜度的推導本質上也是遞推關系求解。常系數(shù)線性齊次遞推的標準解法是特征方程法。比如斐波那契數(shù)列滿足a_n a_{n-1} a_{n-2}特征方程是x2 x 1解得兩個特征根通項就是兩個等比數(shù)列的線性組合。這里有個新手特別容易忽略的坑如果特征方程出現(xiàn)重根通項的形式就要額外乘n否則會少一個線性無關的解。我記得期末考試出了一道題解a_n 4a_{n-1} - 4a_{n-2}特征方程(x-2)2 0重根情況下的通項不是C × 2?而是(C1 C2×n) × 2?。我當時忘了處理重根整道題全扣。這個細節(jié)如果只看書不親手算一遍很難有印象。非齊次遞推的解法則是先解齊次通解再用待定系數(shù)法找特解。課堂上的課時限制非齊次通常只要求右端是多項式、指數(shù)或三角函數(shù)的簡單情形。這塊我沒什么捷徑多練幾道題自然就找到手感。2.4 生成函數(shù)組合計數(shù)的終結技生成函數(shù)是我覺得這門課里最像“魔法”的部分。把一個數(shù)列通過冪級數(shù)打包成一個函數(shù)再用代數(shù)運算來解計數(shù)問題。普通生成函數(shù)的形式是G(x) a0 a1x a2x2 a3x3 ...它的妙處在于兩個生成函數(shù)相乘系數(shù)恰好是原來兩個數(shù)列的卷積。比如求解“從各種面值的硬幣中湊出總金額n元有多少種方法”就可以用不同面值對應的生成函數(shù)相乘積函數(shù)中x?項的系數(shù)就是要答案。我在實際學習中把生成函數(shù)當成一種“無須顯式遞推”的計算工具。遞推方法每求一項都得依賴前一項生成函數(shù)則可以直接給出整個數(shù)列的封包表達式后續(xù)再通過展開或部分分式還原序列。這里要提醒一點組合數(shù)學里用的生成函數(shù)是形式冪級數(shù)不關心收斂半徑只要系數(shù)有限即可所以別拿數(shù)學分析里“函數(shù)級數(shù)必須收斂”的框去套它否則會卡在奇怪的地方。指數(shù)型生成函數(shù)則用來處理帶標號的計數(shù)問題比如集合的排列、有標記的樹的計數(shù)。判斷用普通生成函數(shù)還是指數(shù)型生成函數(shù)我自己的經(jīng)驗是如果對象之間是無標號的組合用普通生成函數(shù)如果對象帶有明顯標號選指數(shù)型生成函數(shù)。2.5 波利亞計數(shù)與組合設計從對稱性去重到工程應用波利亞計數(shù)定理是這門課里壓軸級別的工具。它的核心思想是利用置換群的循環(huán)結構來等價類計數(shù)。最簡單的入門版本是Burnside引理一個集合在群作用下的軌道數(shù)等于群中每個元素不動點數(shù)的平均值。用它對一個正方形涂色四色可選計算本質不同的涂色方案數(shù)時過程大致是先列出正方形的8個對稱置換4個旋轉、4個反射對每個置換統(tǒng)計在四色涂色下保持不變的方案數(shù)最后求平均。這個過程看起來很機械但完全可以體現(xiàn)“等價去重”的通用思路。算法題里判斷兩個狀態(tài)是否本質相同、化學里計算同分異構體數(shù)量用的都是同一套邏輯。組合設計這部分課程時間有限但拉丁方和正交表在實際工程里用處不小。正交表可以用在配置測試的參數(shù)組合上假設系統(tǒng)有4個開關量、每個有3種狀態(tài)全遍歷要81種組合用正交表可能只需要9種就能覆蓋兩兩組合。搞過測試的人都明白這對測試成本的影響是巨大的。3. 實操指南手把手解決幾類經(jīng)典組合問題3.1 用生成函數(shù)求斐波那契數(shù)列的通項這里我先把操作步驟完整寫下來大家可以直接照著推一遍。第一步設斐波那契數(shù)列的生成函數(shù)為F(x) f0 f1x f2x2 f3x3 ...其中f00f11。第二步利用遞推關系f_n f_{n-1} f_{n-2}構造方程。把F(x)乘以x和x2再錯位相減# 用sympy驗證生成函數(shù)推導結果 # 這一步不是程序算法是符號驗證思路 import sympy as sp x sp.symbols(x) n sp.symbols(n, integerTrue, nonnegativeTrue) # 驗證F(x) - xF(x) - x2F(x) x # F(x) x / (1 - x - x2) F x / (1 - x - x**2) series sp.series(F, x, 0, 11) print(sp.expand(series))從結果能看到0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ... 正好是斐波那契數(shù)列。第三步是分拆到部分分式。分母1 - x - x2可以因式分解成(1 - αx)(1 - βx)其中α和β是特征方程的兩個根的倒數(shù)。用待定系數(shù)法拆成兩項每一項都是一個等比數(shù)列的生成函數(shù)直接展開就能讀到通項公式。實際操作中我建議不要只求最后的通項而是把從遞推到生成函數(shù)、再到展開的閉環(huán)走通。這套流程學會了你會理解為什么斐波那契通項里會出現(xiàn)帶根號的表達式也能明白為什么組合數(shù)學方法能直接對遞推求解析解。3.2 錯排問題的容斥解法錯排問題我剛才提過容斥思路這里完整走一遍。設n個元素的錯排數(shù)為D(n)所有排列數(shù)是n!。設事件Ai表示“第i個元素在位置i上”。我們希望計數(shù)的是不在任何Ai中的排列數(shù)。直接計算并集略復雜但容斥公式給了我們一個固定套路# 錯排公式前幾項的快速驗證 import math def derangement(n): total 0 for k in range(n 1): total ((-1) ** k) * math.factorial(n) // math.factorial(k) return total for n in range(1, 8): print(fD({n}) {derangement(n)})代碼跑出來D(1)0, D(2)1, D(3)2, D(4)9, D(5)44, D(6)265, D(7)1854。這幾個數(shù)我在考試前背過因為它們是判斷自己容斥過程有沒有算錯的重要校驗值。這里說說我的踩坑點。用容斥公式時很多同學會把第k項直接寫成(-1)^k × C(n,k) × (n-k)!這沒錯但關鍵在于C(n,k) × (n-k)! n!/k!你沒看錯約分后就是n!除以k!。我第一次做時就因為沒約分算到一半被巨大的階乘數(shù)卡住后來才知道必須化簡之后再算否則手算根本做不下去。3.3 卡特蘭數(shù)的遞推與閉式卡特蘭數(shù)在組合數(shù)學里出現(xiàn)的頻率極高它對應的都是“括號匹配、進出棧序列、二叉樹的形態(tài)”這類結構計數(shù)問題。定義是C0 1, Cn Σ(k0 to n-1) Ck × C(n-1-k)這個遞推式描述了左右子樹的組合關系。要把它化成閉式最漂亮的方法還是生成函數(shù)。設卡特蘭數(shù)的生成函數(shù)為C(x) Σ Cn x?從遞推式可得C(x) 1 xC(x)2解這個二次方程得到C(x) (1 - sqrt(1 - 4x)) / (2x)。這個表達式再通過廣義二項式定理展開x?項的系數(shù)化簡后就是Cn (1/(n1)) × C(2n, n)。實際計算卡特蘭數(shù)時還有個細節(jié)C(2n,n)當n稍大時會非常大但卡特蘭數(shù)本身是整數(shù)。直接用階乘計算容易溢出更穩(wěn)妥的做法是用遞推式逐項迭代每一步先約分或者直接用大整數(shù)類型。我在做算法題時遇到模運算場景還會先取模再乘除但要小心分母的逆元這塊要結合模素數(shù)下的乘法逆元來算。4. 學習實戰(zhàn)這門課怎么學才不白學4.1 算法競賽與課程內(nèi)容的銜接方式成電的ACM集訓隊基本把《組合數(shù)學與應用》當必修課來對待因為競賽中大量題目考查的正是計數(shù)、遞推和概率期望。我記得有一類狀態(tài)壓縮DP題目本質上是給集合的子集計數(shù)推導狀態(tài)轉移方程時用的就是容斥原理效率相差好幾十倍。如果你在打算法競賽或刷筆試算法題我建議把這門課里的幾個工具按優(yōu)先級排序來學遞推關系和特征方程排在第一位因為動態(tài)規(guī)劃的優(yōu)化和復雜度分析離不開它生成函數(shù)排在第二位處理組合遞推和化簡卷積時是利器容斥原理第三它經(jīng)常出現(xiàn)在期望值和概率DP的題目里。波利亞計數(shù)優(yōu)先級可以放低競賽里遇到得少但考研筆試里可能作為區(qū)分題出現(xiàn)。非競賽用途的同學比如研究方向偏系統(tǒng)、偏網(wǎng)絡的同學可以重點學鴿巢原理和容斥的應用場景。我見過一個分布式存儲的場景數(shù)據(jù)分片分布在節(jié)點上要證明“無論怎么分配總有兩個數(shù)據(jù)分片落在同一批節(jié)點上”用的就是鴿巢原理。這種證明在寫一致性方案時特別有說服力。4.2 常見誤區(qū)與避坑清單我總結了自己和身邊同學的踩坑經(jīng)驗下面這幾條你應該提前知道誤區(qū)一只會背公式不會建模型。考試里的題目幾乎不會直接說“請用容斥原理”而是描述一個實際問題需要你先抽象成集合問題。建議平時練習時刻意做審題訓練每道題先不急著算先寫出“設集合A表示…集合B表示…”再套公式。誤區(qū)二生成函數(shù)和普通函數(shù)搞混。生成函數(shù)里x不參與收斂性分析只是一個記錄系數(shù)的載體所以不能拿“x2時這個級數(shù)發(fā)散了”來質疑推導否則你會陷入無意義的糾結。誤區(qū)三忽略邊界情況。遞推式的初始條件必須單獨驗證很多同學特征方程求得很順利但忘記檢查n0或n1時通項公式是否成立。比如某個遞推通項在n0時可能產(chǎn)生0/0型表達式這時需要單獨給初值。誤區(qū)四計算不加校驗。組合數(shù)學題很容易在中間步驟出錯我的習慣是算出結果后用小規(guī)模用例手動檢驗一遍。算錯排時先用n3驗算算卡特蘭數(shù)時先用n4驗算校驗值是2和14如果對不上就回頭檢查。5. 常見問題與學習資源雜談5.1 課程學習中最常見的幾個卡點很多同學卡在生成函數(shù)的“形式冪級數(shù)”概念上。解釋一下普通函數(shù)關注的是x取什么值時收斂到什么數(shù)形式冪級數(shù)關注的是“每次展開出來的系數(shù)是什么”。兩者運算規(guī)則相同但意義完全不同。把意義切換過來生成函數(shù)的很多操作就不會再讓你覺得別扭了。還有同學問到底要不要學群論再學波利亞計數(shù)。就我個人的經(jīng)驗不需要先把群論學完整。你只需要建立幾個基本概念集合、置換、合成運算和循環(huán)分解就足夠理解Burnside引理了。等以后需要深入再補群論不遲。常見卡點典型表現(xiàn)應對策略套路不明拿到題不知從哪下手先判斷類型求個數(shù)用計數(shù)原理求排除用容斥求通項用生成函數(shù)公式記混二項式系數(shù)和錯排公式混淆親手把公式推一遍不要死記重根漏解特征方程重根只寫一個解遇到判別式為0時主動在通項里補n因子冪級數(shù)展開出錯部分分式系數(shù)求不對用代入具體數(shù)值的方法驗算待定系數(shù)5.2 推薦的學習順序與輔助資料如果你要系統(tǒng)自學這門課我建議的順序是先復習高中排列組合然后按“計數(shù)基礎→容斥原理→鴿巢原理→遞推關系→生成函數(shù)→波利亞計數(shù)”的順序推進。中間可以隨時穿插一些算法題來鞏固比如在學完生成函數(shù)后去OJ上找?guī)椎馈氨嘲嫈?shù)”類題目練手。教材方面成電這門課主要參考的是組合數(shù)學領域的經(jīng)典教材但這套內(nèi)容在世界范圍內(nèi)都很成熟。如果想補充視野可以看看MIT的公開課組合數(shù)學講義網(wǎng)上能找到。不過在復習備考時還是以課堂講義和往年真題為主公開課適合培養(yǎng)直覺不適合突擊應試。6. 這門課在工程和科研中的真實價值6.1 從課堂到企業(yè)的思維遷移畢業(yè)后回頭看我最大的感觸是這門課訓練的是“有限條件下的系統(tǒng)規(guī)劃能力”。處理真實系統(tǒng)問題時資源總是有限的狀態(tài)空間總是巨大的怎么快速判斷“方案數(shù)量是否可控”“是否存在不可避免的沖突”這些思路和組合數(shù)學高度重合。我舉個具體例子灰度發(fā)布時要把用戶分成若干實驗組要求任意兩個功能特性之間的交叉組合都能被覆蓋到又要控制總組數(shù)不能太大。這個問題的數(shù)學模型就是正交表設計本質上就是組合設計里的內(nèi)容。不懂組合數(shù)學的人可能靠拍腦袋決定分組學了這門課之后就知道用現(xiàn)成的正交表規(guī)模來評估需要多少組。再舉個算法例子設計一個Bloom Filter時要估算誤判率與位數(shù)組大小、哈希函數(shù)數(shù)量的關系。這個估算過程里全是組合數(shù)學的影子——插入一個元素后某個比特位仍為0的概率是個典型的不放回抽樣計數(shù)問題。誤差分析、參數(shù)選擇全部建立在組合計數(shù)之上。6.2 給科研新手的一點建議如果你讀研期間要做理論研究組合數(shù)學幾乎是必備語言。做算法分析要算復雜度做信息論要算編碼數(shù)量邊界做密碼學要算碰撞概率這些都離不開組合工具。我建議科研方向的同學把生成函數(shù)和遞推關系練到條件反射的水準因為很多復雜序列的性質都可以從這兩個工具出發(fā)被快速推導出來。另外數(shù)學建模競賽里的“優(yōu)化與方案選擇”問題也經(jīng)常需要組合計數(shù)來估計搜索空間的大小。搞清楚狀態(tài)空間有多大才談得上設計什么樣的搜索剪枝策略。這塊內(nèi)容我最后再補充一點個人看法學組合數(shù)學的時候別把它當成純數(shù)學課來學。它更像是思想工具箱每個工具都有它適合的場景考試只是檢驗你有沒有把這個工具箱整理好。整理得越好后面用起來越順手。