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

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

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

3、S, Tsinghua)July, 20197 / 50減法原理常具用有于這：種當(dāng)性直質(zhì)接的統(tǒng)事計(jì)物具個(gè)有數(shù)一，種再性用質(zhì)總的數(shù)事減物去個(gè)這數(shù)個(gè)較值為。困難時(shí)，考慮統(tǒng)計(jì)不 學(xué)例沒如來：。班上一共有 n 個(gè)同學(xué)，老師點(diǎn)名，到了 m 個(gè)，則有 n m 個(gè)同組合數(shù)學(xué)及計(jì)數(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é)及計(jì)數(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證明：（考慮每個(gè)元素對(duì)等式兩邊的貢獻(xiàn)）組合數(shù)學(xué)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 20199 / 50容斥原理等式兩邊對(duì)全集 S 取補(bǔ)集，記 = S，得到n A A |J|JA = | | S ¯ |+1|(1)=(1)ijj i=1 =J1,.,njJJ1,.,njJ組合數(shù)學(xué)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201

5、910 / 50容斥原理等式兩邊對(duì)全集 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é)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201910 / 50容斥原理常反用），于有：時(shí)直也接可算用并摩集根大律小轉(zhuǎn)較換為為困補(bǔ)難集，的但交是或算并交。集大小相對(duì)容易（或者相例如：求 1 200 中能被 2, 3, 5 中任意一個(gè)整除的數(shù)字個(gè)數(shù)。組合數(shù)學(xué)及計(jì)數(shù)will7101 (CS, Tsinghu

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

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

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

9、中選出 k 個(gè)，無視順序，有多少種不同的選法？假如按照剛才的排列數(shù)來算，那么每種方案都被重復(fù)算了 k! 次，所以只要除以 k!，就得到答案：( )nn!k= C =nkk! (n k)!組合數(shù)學(xué)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201914 / 50一些性質(zhì)( )n n!n (n (n k × 1) × · · · × + 1)=kk! (n k)!k!組合數(shù)學(xué)及計(jì)數(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é)及計(jì)數(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é)及計(jì)數(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 時(shí)，( )() ()nn 1n k 1=+kk 1組合數(shù)學(xué)及計(jì)數(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 時(shí)，( )()()nn 1n k1=+kk 1( )()k nn 1=n kk 1組合數(shù)學(xué)及計(jì)數(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í)際中，由于數(shù)字很大，一般需要取模。乘如，果然需后

13、要分計(jì)別算代一入定分范式圍求內(nèi)出的答多案個(gè)。組合數(shù)，也可以預(yù)先計(jì)算出 1 n 的階組合數(shù)學(xué)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201916 / 50楊輝三（帕斯卡三）011234501211121551510101. . .組合數(shù)學(xué)及計(jì)數(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é)及計(jì)數(shù)will7101 (C

14、S, Tsinghua)July, 201918 / 50二項(xiàng)式定理( )( )( )( )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é)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 2019

15、19 / 50數(shù)學(xué)題()()()nn2n22+ · · · +2n 113組合數(shù)學(xué)及計(jì)數(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é)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201920 / 50數(shù)學(xué)題( )()()()nn + 11n + 22n + m m

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

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

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

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

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

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

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

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

25、圍（內(nèi)x）枚，舉我元們素往，往計(jì)需算要它安們排一例個(gè)如合：適的順序來計(jì)算。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é)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201929 / 50目錄基本計(jì)數(shù)原理組合數(shù)123 計(jì)數(shù)技巧例題選講4組合數(shù)學(xué)及計(jì)數(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對(duì) 109 + 7 取模，n 109。組合數(shù)學(xué)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201931 / 50數(shù)字求和 sol樸素做法實(shí)際上是先枚舉數(shù)，再枚舉每一位。組合數(shù)學(xué)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201932 / 50數(shù)字求和 sol樸素做法實(shí)際上是先枚舉數(shù)，再枚舉每一位?？即饝]案這的樣貢的獻(xiàn)順，序最：后先加枚起舉來每。個(gè)數(shù)碼，再計(jì)算它出現(xiàn)了多少次，得到它對(duì)組合數(shù)學(xué)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201932 / 50數(shù)字求和 sol樸素做法實(shí)際上是先枚

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

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

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

30、塊，變?yōu)橐?guī)模為的子問題。第n 1n 1 1n 1 塊可以染 m 2 種顏色。組合數(shù)學(xué)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201934 / 50圓盤染色 sol的由顏于色形：成了環(huán)，不能直接用乘法原理來計(jì)算?？紤]第 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é)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201934 / 50錯(cuò)位排列有 n 個(gè)信封和 n 封信，一一對(duì)應(yīng)，求把每封信都裝錯(cuò)信封的方案數(shù)。組合數(shù)學(xué)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201935 / 50錯(cuò)位排列 sol1利用容斥原理，每都裝錯(cuò)，一共為 n 個(gè)限制條件，考慮它們補(bǔ)集的交：對(duì)于指定的 k 封信，要求它們都裝對(duì)，方案數(shù)為 (n k；而指定 k)!封信有種方案。( )nk組合數(shù)學(xué)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 2019 36 / 50錯(cuò)位排列 sol1利用容斥原理，每都裝錯(cuò)，一共為 n 個(gè)限制條件

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

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

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

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

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

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

38、種能。發(fā)如生果越相獄鄰。房間的犯人的宗教相同，有多少組合數(shù)學(xué)及計(jì)數(shù)will7101 (CS, Tsinghua)July, 201940 / 50 HNOI2008 越獄 sol減法原理，計(jì)算不發(fā)生越獄的情況數(shù)為 m ·(m 1)，所有情況數(shù)為n1，于是答案為 mn m · (m 1)n1。mn組合數(shù)學(xué)及計(jì)數(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é)及計(jì)數(shù)will7101 (CS, Ts

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