組合數(shù)學(xué)與計數(shù)

1、組合數(shù)學(xué)及計數(shù)will7101CS, TsinghuaJuly, 2019組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 20191 / 50目錄基本計數(shù)原理組合數(shù)123 計數(shù)技巧例題選講4組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 20192 / 50加法原理若 A B = ，則|A B| = |A| + |B|組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 20193 / 50加法原理常用于分類計數(shù)，考慮不同情況。注意不重不漏。例如：吃套餐，需要選一份披薩或意面，披薩有 n 種，意面有 m 種，則共有 n + m

2、種方案。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 20194 / 50乘法原理|A × B| = |A| · |B|組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 20195 / 50乘法原理常不用影于響分。步計數(shù)，考慮做一件事的不同階段。需要各階段相互獨立，互 例案如。：吃套餐，主菜有 n 種，配菜有 m 種，任意搭配，則共有 nm 種方組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 20196 / 50減法原理記 S 為全集，則|A| = |S| |S A|組合數(shù)學(xué)及計數(shù)will7101 (C

3、S, Tsinghua)July, 20197 / 50減法原理常具用有于這：種當(dāng)性直質(zhì)接的統(tǒng)事計物具個有數(shù)一，種再性用質(zhì)總的數(shù)事減物去個這數(shù)個較值為。困難時，考慮統(tǒng)計不 學(xué)例沒如來：。班上一共有 n 個同學(xué)，老師點名，到了 m 個，則有 n m 個同組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 20198 / 50容斥原理|A B| =|A| + |B| |A B|A B C| =|A| + |B| + |C| |A B| |A C| |B C|+ |A B C|組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 20199 / 50容斥原理|A

4、 B| =|A| + |B| |A B|A B C| =|A| + |B| + |C| |A B| |A C| |B C|+ |A B C|更一般的形式：n A A |J|+1=(1)ij ijJ=J1,.,n=1證明：（考慮每個元素對等式兩邊的貢獻(xiàn)）組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 20199 / 50容斥原理等式兩邊對全集 S 取補(bǔ)集，記 = S，得到n A A |J|JA = | | S ¯ |+1|(1)=(1)ijj i=1 =J1,.,njJJ1,.,njJ組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201

5、910 / 50容斥原理等式兩邊對全集 S 取補(bǔ)集，記 = S，得到n A A |J|JA = | | S ¯ |+1|(1)=(1)ijj i=J1,.,njJJ1,.,njJ=1或者n |JA =A ¯ |(1)ij jJ iJ1,.,n=1組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201910 / 50容斥原理常反用），于有：時直也接可算用并摩集根大律小轉(zhuǎn)較換為為困補(bǔ)難集，的但交是或算并交。集大小相對容易（或者相例如：求 1 200 中能被 2, 3, 5 中任意一個整除的數(shù)字個數(shù)。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghu

6、a)July, 2019 11 / 50容斥原理常反用），于有：時直也接可算用并摩集根大律小轉(zhuǎn)較換為為困補(bǔ)難集，的但交是或算并交。集大小相對容易（或者相 例如：求 1 200 中能被 2, 3, 5 中任意一個整除的數(shù)字個數(shù)。利用容斥原理，分別計算 2, 3, 5, 2 × 3, 2 × 5, 3 × 5, 2 × 3 × 5 的倍數(shù)個數(shù)， 根據(jù) 1 n 中 k 的倍數(shù)個數(shù)為，得到答案nk2002002002002002001520030+235610=100 + 66 + 40 33 20 13 + 6=146組合數(shù)學(xué)及計數(shù)will7101

7、(CS, Tsinghua)July, 201911 / 50目錄基本計數(shù)原理組合數(shù)123 計數(shù)技巧例題選講4組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201912 / 50全排列與排列將 n 個物品排成一行，有多少種不同的順序？1 × 2 × 3 × · · · × n = n!組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 2019 13 / 50全排列與排列將 n 個物品排成一行，有多少種不同的順序？1 × 2 × 3 × ·

8、 · · × n = n!從 n 個物品中選出 k 個排成一行，有多少種不同的順序？n!(n k + 1) × (n k + 2) × (n k + 3) × · · · × n =證明：（一個一個選，乘法原理）(n k)!組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201913 / 50組合數(shù)從 n 個物品中選出 k 個，無視順序，有多少種不同的選法？組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 2019 14 / 50組合數(shù)從 n 個物品

9、中選出 k 個，無視順序，有多少種不同的選法？假如按照剛才的排列數(shù)來算，那么每種方案都被重復(fù)算了 k! 次，所以只要除以 k!，就得到答案：( )nn!k= C =nkk! (n k)!組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201914 / 50一些性質(zhì)( )n n!n (n (n k × 1) × · · · × + 1)=kk! (n k)!k!組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 2019 15 / 50一些性質(zhì)( )n n!n (n (n k × 1

10、) × · · · × + 1)=kk! (n k)!k!( )( )( )nnnn(n 1)= 1,= n,=0122組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201915 / 50一些性質(zhì)( )n n!n (n (n k × 1) × · · · × + 1)=kk! (n k)!k!( )( )( )nnnn(n 1)= 1,= n,=0122( )()nn=kn k組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201915

11、 / 50一些性質(zhì)( )n n!n (n (n k × 1) × · · · × + 1)=kk! (n k)!k!( )( )( )nnnn(n 1)= 1,= n,=0122( )()nn=kn k當(dāng) k > 0 時，( )() ()nn 1n k 1=+kk 1組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201915 / 50一些性質(zhì)( )n n!n × (n 1) × · · · × (n k + 1)=kk! (n k)!k!( )

12、( )( )nnnn(n 1)= n= 1,=0122( )()nn=kn k當(dāng) k > 0 時，( )()()nn 1n k1=+kk 1( )()k nn 1=n kk 1組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201915 / 50組合數(shù)的定義求法int C(int n, int k) int forp = 1, q = 1;(int p *= (int q *=i = n - k + 1; i <= n; +i)i;i = 1; i <= k; +i) i;/ q;forreturn p實際中，由于數(shù)字很大，一般需要取模。乘如，果然需后

13、要分計別算代一入定分范式圍求內(nèi)出的答多案個。組合數(shù)，也可以預(yù)先計算出 1 n 的階組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201916 / 50楊輝三（帕斯卡三）011234501211121551510101. . .組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201917 / 50組合數(shù)的遞推求法for (int i = 0; i < n; Ci0 = 1;for (int j = 1; j Cij = Ci同上，一般需要取模。+i) <= i; +j) -1j -1+ Ci-1j;組合數(shù)學(xué)及計數(shù)will7101 (C

14、S, Tsinghua)July, 201918 / 50二項式定理( )( )( )( )nnnnnnnnn(x + yx +xy +xy + · · · +y12 2) =n012( )nnnk kx y=kk=0代入 x = 1, y = 1，得到( )( )( )( )nnnnn+ · · · += 2n012代入 x = 1, y = 1，得到( )( )( )( )nnnnn+ · · · + (1)= 0n012組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 2019

15、19 / 50數(shù)學(xué)題()()()nn2n22+ · · · +2n 113組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201920 / 50數(shù)學(xué)題()()()nn2n22+ · · · +2n 113()()()()n 1n 1n 1n 12222=+ · · ·0123()()n 1n 122+2n 22n 1=22n1組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201920 / 50數(shù)學(xué)題( )()()()nn + 11n + 22n + m m

16、+ · · · +0組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201921 / 50數(shù)學(xué)題( )()()()nn + 11n + 22n + m m+ · · · +0( )()()()nn + 1n + 2n + m=+ · · · +nnnn()()()n + 1n + 1n + 2n + m n=+ · · · +n + 1nn()()()n + 2n + 2n + m+ · · · +=+n + 1nn()(

17、)n + m + 1n + 1n + m + 1m=組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201921 / 50目錄基本計數(shù)原理組合數(shù)123 計數(shù)技巧例題選講4組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201922 / 50等價替代當(dāng)法我。具們體需來要講計，算我一們些構(gòu)帶造特一殊個條雙件射的（方一案一數(shù)映時射，）可，以將用每一一些種等原價問替題代的的方方案映射為新問題的一種方案，并使答案更容易計算。常用的有捆綁法、插空法、隔板法等。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201923 / 50捆綁法

18、也個稱整整體體來法進(jìn)，行在計計數(shù)數(shù)。時，如果要求若干物品相鄰，則可以將它們作為一組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201924 / 50捆綁法也個稱整整體體來法進(jìn)，行在計計數(shù)數(shù)。時，如果要求若干物品相鄰，則可以將它們作為一多例少如種：排AB列C方DE法五。個人要排隊，A 和 B 要相鄰，C 和 D 要相鄰，求有組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201924 / 50捆綁法也個稱整整體體來法進(jìn)，行在計計數(shù)數(shù)。時，如果要求若干物品相鄰，則可以將它們作為一多例少如種：排AB列C方DE法五。個人要排隊，A 和 B 要相鄰，C

19、和 D 要相鄰，求有方首案先數(shù)將為AB、CD 分別看成一個整體，然后變成 3 個元素的排列問題，然后考慮 AB、CD 內(nèi)部的相對順序，共有 4 種情況，3! = 6最終答案為 6 × 4 = 24。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201924 / 50插空法如品果插要入求空若當(dāng)干中物，品進(jìn)兩行兩計不數(shù)相。鄰，可以先將其他物品放好，然后將這些物組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201925 / 50插空法如品果插要入求空若當(dāng)干中物，品進(jìn)兩行兩計不數(shù)相。鄰，可以先將其他物品放好，然后將這些物例如：ABCDEFG

20、 七個人要排隊，ABC 三個人兩兩不相鄰，求方案數(shù)。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201925 / 50插空法如品果插要入求空若當(dāng)干中物，品進(jìn)兩行兩計不數(shù)相。鄰，可以先將其他物品放好，然后將這些物例如：ABCDEFG 七個人要排隊，ABC 三個人兩兩不相鄰，求方案數(shù)。先將剩下四個人排好，有 4! = 24 種方案；然后將 ABC 三個人插入 5個空當(dāng)中，有 5 × 4 × 3 = 60 種方案，最終答案為 24 × 60 = 1440。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201925 /

21、 50隔板法將不可區(qū)分物品分配問題/不定方程整數(shù)解問題轉(zhuǎn)化為插板組合問題。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201926 / 50隔板法將不可區(qū)分物品分配問題/不定方程整數(shù)解問題轉(zhuǎn)化為插板組合問題。 例案如數(shù)：。把 n 個相同的蘋果分給 k 個人，要求每個人至少分到一個，求方組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201926 / 50隔板法將不可區(qū)分物品分配問題/不定方程整數(shù)解問題轉(zhuǎn)化為插板組合問題。 例案如數(shù)：。把 n 個相同的蘋果分給 k 個人，要求每個人至少分到一個，求方我個們?nèi)税逊诌@到的n 部個分蘋，果而擺每成種一

22、插排板，的從方左案往和右原依來次的插每入一k種分1 配塊方隔案板是，一代一表對每應(yīng)最的終，答案k 為1 塊隔板插入 n 1 個空當(dāng)中（不能插在最左和最右），所以()n 1k 1組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201926 / 50隔板法如果改一改原問題，允許有人分到 0 個，那么答案應(yīng)該怎么改呢？組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201927 / 50隔板法如果改一改原問題，允許有人分到 0 個，那么答案應(yīng)該怎么改呢？剛才的問題可以抽象為數(shù)學(xué)模型：求方程x1 + x2 + · · · +

23、 xk = n的整數(shù)解，滿足 xi 1。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201927 / 50隔板法如果改一改原問題，允許有人分到 0 個，那么答案應(yīng)該怎么改呢？剛才的問題可以抽象為數(shù)學(xué)模型：求方程x1 + x2 + · · · + xk = n的整數(shù)解，滿足 xi 1。求如方果程限制改成 xi 0，我們可以設(shè) k 個新變量 yi = xi + 1 1，轉(zhuǎn)化為y1 + y2 + · · · + yk = n + k的整數(shù)解，結(jié)合剛才的結(jié)論，得到答案()n + k 1k 1組合數(shù)學(xué)及計數(shù)will7

24、101 (CS, Tsinghua)July, 201927 / 50改變計數(shù)目標(biāo)如法果轉(zhuǎn)直換接成按容照易題求意的來目計標(biāo)數(shù)。比較困難，可以嘗試通過減法、容斥原理等方組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201928 / 50改變枚舉順序很的多和時。候直，接計按數(shù)照題意做來的做基顯本然上只是能：拿在到某暴個力范分圍（內(nèi)x）枚，舉我元們素往，往計需算要它安們排一個合適的順序來計算。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 2019 29 / 50改變枚舉順序很的多和時。候直，接計按數(shù)照題意做來的做基顯本然上只是能：拿在到某暴個力范分

25、圍（內(nèi)x）枚，舉我元們素往，往計需算要它安們排一例個如合：適的順序來計算。nnnnn max i, j =kmax i, j = k·i=1 j=1k=1i=1 j=1n=k · (2k 1)k=1nn + 1)k 2k2=(2k=14n3 + 3n2 n=6組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201929 / 50目錄基本計數(shù)原理組合數(shù)123 計數(shù)技巧例題選講4組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201930 / 50數(shù)字求和求設(shè) f(x) 為 x 在十進(jìn)制下的各位數(shù)字之和，例如 f(123) = 1

26、 + 2 + 3 = 6，10nf(i)i=0對 109 + 7 取模，n 109。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201931 / 50數(shù)字求和 sol樸素做法實際上是先枚舉數(shù)，再枚舉每一位。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201932 / 50數(shù)字求和 sol樸素做法實際上是先枚舉數(shù)，再枚舉每一位。考答慮案這的樣貢的獻(xiàn)順，序最：后先加枚起舉來每。個數(shù)碼，再計算它出現(xiàn)了多少次，得到它對組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201932 / 50數(shù)字求和 sol樸素做法實際上是先枚

27、舉數(shù)，再枚舉每一位。考答慮案這的樣貢的獻(xiàn)順，序最：后先加枚起舉來每。個數(shù)碼，再計算它出現(xiàn)了多少次，得到它對再來看每個數(shù)碼出現(xiàn)了多少次：0 10n 相當(dāng)于每一位都可以任取 0 9碼，于是對于每一位上的每個數(shù)碼，它出現(xiàn)的次數(shù)等于其他位任取的方案數(shù) 10，然后一共有 n 位，所以每個數(shù)碼出現(xiàn)的次數(shù)為n1n · 10，于是最終答案為n1(1 + 2 + · · · + 9) · n · 10n1組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201932 / 50圓盤染色顏一色個不圓同盤，分求為方n 案個數(shù)扇。形，用

28、m 種顏色去給染色，要求相鄰的兩個扇形組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201933 / 50圓盤染色 sol的由顏于色形：成了環(huán)，不能直接用乘法原理來計算?？紤]第 n 塊和第 n 2 塊組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201934 / 50圓盤染色 sol的由顏于色形：成了環(huán)，不能直接用乘法原理來計算?？紤]第 n 塊和第 n 2 塊如果顏色相同，則利用整體法看成一塊，變?yōu)橐?guī)模為 n 2 的子問題。第 n 1 塊可以染 m 1 種顏色。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 20193

29、4 / 50圓盤染色 sol的由顏于色形：成了環(huán)，不能直接用乘法原理來計算?？紤]第 n 塊和第 n 2 塊題如。果第顏色n 相同塊，可則以利染用整m體法看種成顏一色塊。，變?yōu)橐?guī)模為 n 2 的子問如果顏色不同1 ，無視第塊，變?yōu)橐?guī)模為的子問題。第n 1n 1 1n 1 塊可以染 m 2 種顏色。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201934 / 50圓盤染色 sol的由顏于色形：成了環(huán)，不能直接用乘法原理來計算。考慮第 n 塊和第 n 2 塊題如。果第顏色n 相同塊，可則以利染用整m體法看種成顏一色塊。，變?yōu)橐?guī)模為 n 2 的子問如果顏色不 同1 ，無視第

30、塊，變?yōu)橐?guī)模為的子問題。第n 1n 1 1n 1 塊可以染 m 2 種顏色。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201934 / 50圓盤染色 sol的由顏于色形：成了環(huán)，不能直接用乘法原理來計算。考慮第 n 塊和第 n 2 塊題如。果第顏色n 相同塊，可則以利染用整m體法看種成顏一色塊。，變?yōu)橐?guī)模為 n 2 的子問如果顏色不同1 ，無視第塊，變?yōu)橐?guī)模為的子問題。第n 1n 1 1n 1 塊可以染 m 2 種顏色。綜上，得到轉(zhuǎn)移方程f(n) = (m 1)f(n 2) + (m 2)f(n 1)初始條件為 f(1) = 0, f(2) = m(m 1)。組合

31、數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201934 / 50錯位排列有 n 個信封和 n 封信，一一對應(yīng)，求把每封信都裝錯信封的方案數(shù)。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201935 / 50錯位排列 sol1利用容斥原理，每都裝錯，一共為 n 個限制條件，考慮它們補(bǔ)集的交：對于指定的 k 封信，要求它們都裝對，方案數(shù)為 (n k；而指定 k)!封信有種方案。( )nk組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 2019 36 / 50錯位排列 sol1利用容斥原理，每都裝錯，一共為 n 個限制條件

32、，考慮它們補(bǔ)集的交：對于指定的 k 封信，要求它們都裝對，方案數(shù)為 (n k；而指定 k)!封信有種方案。( )nk于是答案為( )nnnn!· k!kk(n k)! =(1)(1)kk=0k=0組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201936 / 50錯位排列 sol2不也妨可設(shè)以為用遞推來做。對于 n 號信件，它必然裝在 1 n 1 號信封中，1 號（這些情況都是等價的，最后再乘 n 1），再來考慮 1 號信件裝在哪里：組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201937 / 50錯位排列 sol2不也妨可設(shè)以為

33、用遞推來做。對于 n 號信件，它必然裝在 1 n 1 號信封中，1 號（這些情況都是等價的，最后再乘 n 1），再來考慮 1 號信件裝在哪里：如果裝在 n 號信封中，則剩下 n 2 封信和信封構(gòu)成一個規(guī)模n 2 的子問題；組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201937 / 50錯位排列 sol2不也妨可設(shè)以為用遞推來做。對于 n 號信件，它必然裝在 1 n 1 號信封中，1 號（這些情況都是等價的，最后再乘 n 1），再來考慮 1 號信件裝在哪里：如果裝在 n 號信封中，則剩下 n 2 封信和信封構(gòu)成一個規(guī)模n 2 的子問題；號如去果除裝，在 k 號信封中

34、（k = n），使用整體法，這種情況等價于將 1n 號信件直接裝進(jìn) k 號的情況，于是對應(yīng)了規(guī)模為 n 1的子問題。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201937 / 50錯位排列 sol2不也妨可設(shè)以為用遞推來做。對于 n 號信件，它必然裝在 1 n 1 號信封中，1 號（這些情況都是等價的，最后再乘 n 1），再來考慮 1 號信件裝在哪里：如果裝在 n 號信封中，則剩下 n 2 封信和信封構(gòu)成一個規(guī)模n 2 的子問題；號如去果除裝，在 k 號信封中（k = n），使用整體法，這種情況等價于將 1n 號信件直接裝進(jìn) k 號的情況，于是對應(yīng)了規(guī)模為 n 1

35、的子問題。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201937 / 50錯位排列 sol2不也妨可設(shè)以為用遞推來做。對于 n 號信件，它必然裝在 1 n 1 號信封中，1 號（這些情況都是等價的，最后再乘 n 1），再來考慮 1 號信件裝在哪里：如果裝在 n 號信封中，則剩下 n 2 封信和信封構(gòu)成一個規(guī)模n 2 的子問題；號如去果除裝，在 k 號信封中（k = n），使用整體法，這種情況等價于將 1n 號信件直接裝進(jìn) k 號的情況，于是對應(yīng)了規(guī)模為 n 1的子問題。得到遞推式p(n) = (n 1) · p(n 1) + p(n 2)初始條件為 p(

36、1) = 0, p(2) = 1。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201937 / 50 SDOI2016 排列計數(shù)求度為 n 的排列個數(shù)，滿足恰好有 m 個數(shù)字沒有錯位。T 組詢問，T 5 × 105，n, m 106。答案對 109 + 7 取模。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201938 / 50 SDOI2016 排列計數(shù) sol有做錯m位個排沒列有。錯于位是，答就案相為當(dāng)于先選出 m 個固定下來，然后剩下 n m 個( )np(n m)m組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghu

37、a)July, 201939 / 50 SDOI2016 排列計數(shù) sol有做錯m位個排沒列有。錯于位是，答就案相為當(dāng)于先選出 m 個固定下來，然后剩下 n m 個們本的題乘主法要逆難元度，在一于個快技速巧求是組利合用數(shù)，可以預(yù)先處理出 1 n 的階乘以及它(n 1)!)1 = (n!)1 · n來遞推計算逆元，可以做到線性。( )np(n m)m組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201939 / 50 HNOI2008 越獄1 . . . n 的 n 個房間，每個房間關(guān)押一個犯人，有 m種就監(jiān)可獄能有發(fā)連生續(xù)越編獄號，為求可能信仰種其狀中態(tài)一可

38、種能。發(fā)如生果越相獄鄰。房間的犯人的宗教相同，有多少組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201940 / 50 HNOI2008 越獄 sol減法原理，計算不發(fā)生越獄的情況數(shù)為 m ·(m 1)，所有情況數(shù)為n1，于是答案為 mn m · (m 1)n1。mn組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201941 / 50 NOIP2016 組合數(shù)問題給出正i整數(shù) k，有 t 組詢問，每次求 0 i n, 0 j mini, m 中有多少 (j) 是 k 的倍數(shù)。組合數(shù)學(xué)及計數(shù)will7101 (CS, Ts

39、inghua)July, 201942 / 50 NOIP2016 組合數(shù)問題 sol由于k 在每組詢問中是一樣的，求有多少是 k 的倍數(shù)，實際上就是求在模 k 意義下有多少個等于零。所以可以通過遞推的方式求出 (N, M) 范圍內(nèi)所有的組合數(shù)（模 k），然后通過二維前綴和來算出每個 (n) 的答, m案。注進(jìn)意答：案由。于題目中 j mini, m 而不是 j m，不能將 j > i 的部分算組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201943 / 50 JSOI2015 子集選取給出 |S| = n 和 k，要求選出 S 的個子集，排成k(k+1) 2A1,1 A2,1 A3,1A2,2A3,2A3,3. . .Ak,1且滿足 AAk,kA· · ·，A。（每個集合是左和上的子集）i,j i1,ji,j Ai,j1求方案數(shù)對 109 + 7 取模，n, k 109。組合數(shù)學(xué)及計數(shù)will7101 (CS, Tsinghua)July, 201944 / 50 JSOI2015 子集選取 sol直立接的做，似可乎以非使常用棘乘手法，原觀理察，到算一出個n 性=質(zhì)1 ：時集的合答的案每，個然元后素做對n于次答冪案。是獨對n = 1