组合数学与计数

1、组合数学及计数will7101CS, TsinghuaJuly, 2019组合数学及计数will7101 (CS, Tsinghua)July, 20191 / 50目录基本计数原理组合数123 计数技巧例题选讲4组合数学及计数will7101 (CS, Tsinghua)July, 20192 / 50加法原理若 A B = ，则|A B| = |A| + |B|组合数学及计数will7101 (CS, Tsinghua)July, 20193 / 50加法原理常用于分类计数，考虑不同情况。注意不重不漏。例如：吃套餐，需要选一份披萨或意面，披萨有 n 种，意面有 m 种，则共有 n + m

2、种方案。组合数学及计数will7101 (CS, Tsinghua)July, 20194 / 50乘法原理|A × B| = |A| · |B|组合数学及计数will7101 (CS, Tsinghua)July, 20195 / 50乘法原理常不用影于响分。步计数，考虑做一件事的不同阶段。需要各阶段相互独立，互 例案如。：吃套餐，主菜有 n 种，配菜有 m 种，任意搭配，则共有 nm 种方组合数学及计数will7101 (CS, Tsinghua)July, 20196 / 50减法原理记 S 为全集，则|A| = |S| |S A|组合数学及计数will7101 (C

3、S, Tsinghua)July, 20197 / 50减法原理常具用有于这：种当性直质接的统事计物具个有数一，种再性用质总的数事减物去个这数个较值为。困难时，考虑统计不 学例没如来：。班上一共有 n 个同学，老师点名，到了 m 个，则有 n m 个同组合数学及计数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|组合数学及计数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证明：（考虑每个元素对等式两边的贡献）组合数学及计数will7101 (CS, Tsinghua)July, 20199 / 50容斥原理等式两边对全集 S 取补集，记 = S，得到n A A |J|JA = | | S ¯ |+1|(1)=(1)ijj i=1 =J1,.,njJJ1,.,njJ组合数学及计数will7101 (CS, Tsinghua)July, 201

5、910 / 50容斥原理等式两边对全集 S 取补集，记 = 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组合数学及计数will7101 (CS, Tsinghua)July, 201910 / 50容斥原理常反用），于有：时直也接可算用并摩集根大律小转较换为为困补难集，的但交是或算并交。集大小相对容易（或者相例如：求 1 200 中能被 2, 3, 5 中任意一个整除的数字个数。组合数学及计数will7101 (CS, Tsinghu

6、a)July, 2019 11 / 50容斥原理常反用），于有：时直也接可算用并摩集根大律小转较换为为困补难集，的但交是或算并交。集大小相对容易（或者相 例如：求 1 200 中能被 2, 3, 5 中任意一个整除的数字个数。利用容斥原理，分别计算 2, 3, 5, 2 × 3, 2 × 5, 3 × 5, 2 × 3 × 5 的倍数个数， 根据 1 n 中 k 的倍数个数为，得到答案nk2002002002002002001520030+235610=100 + 66 + 40 33 20 13 + 6=146组合数学及计数will7101

7、(CS, Tsinghua)July, 201911 / 50目录基本计数原理组合数123 计数技巧例题选讲4组合数学及计数will7101 (CS, Tsinghua)July, 201912 / 50全排列与排列将 n 个物品排成一行，有多少种不同的顺序？1 × 2 × 3 × · · · × n = n!组合数学及计数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)!组合数学及计数will7101 (CS, Tsinghua)July, 201913 / 50组合数从 n 个物品中选出 k 个，无视顺序，有多少种不同的选法？组合数学及计数will7101 (CS, Tsinghua)July, 2019 14 / 50组合数从 n 个物品

9、中选出 k 个，无视顺序，有多少种不同的选法？假如按照刚才的排列数来算，那么每种方案都被重复算了 k! 次，所以只要除以 k!，就得到答案：( )nn!k= C =nkk! (n k)!组合数学及计数will7101 (CS, Tsinghua)July, 201914 / 50一些性质( )n n!n (n (n k × 1) × · · · × + 1)=kk! (n k)!k!组合数学及计数will7101 (CS, Tsinghua)July, 2019 15 / 50一些性质( )n n!n (n (n k × 1

10、) × · · · × + 1)=kk! (n k)!k!( )( )( )nnnn(n 1)= 1,= n,=0122组合数学及计数will7101 (CS, Tsinghua)July, 201915 / 50一些性质( )n n!n (n (n k × 1) × · · · × + 1)=kk! (n k)!k!( )( )( )nnnn(n 1)= 1,= n,=0122( )()nn=kn k组合数学及计数will7101 (CS, Tsinghua)July, 201915

11、 / 50一些性质( )n n!n (n (n k × 1) × · · · × + 1)=kk! (n k)!k!( )( )( )nnnn(n 1)= 1,= n,=0122( )()nn=kn k当 k > 0 时，( )() ()nn 1n k 1=+kk 1组合数学及计数will7101 (CS, Tsinghua)July, 201915 / 50一些性质( )n n!n × (n 1) × · · · × (n k + 1)=kk! (n k)!k!( )

12、( )( )nnnn(n 1)= n= 1,=0122( )()nn=kn k当 k > 0 时，( )()()nn 1n k1=+kk 1( )()k nn 1=n kk 1组合数学及计数will7101 (CS, Tsinghua)July, 201915 / 50组合数的定义求法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实际中，由于数字很大，一般需要取模。乘如，果然需后

13、要分计别算代一入定分范式围求内出的答多案个。组合数，也可以预先计算出 1 n 的阶组合数学及计数will7101 (CS, Tsinghua)July, 201916 / 50杨辉三（帕斯卡三）011234501211121551510101. . .组合数学及计数will7101 (CS, Tsinghua)July, 201917 / 50组合数的递推求法for (int i = 0; i < n; Ci0 = 1;for (int j = 1; j Cij = Ci同上，一般需要取模。+i) <= i; +j) -1j -1+ Ci-1j;组合数学及计数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组合数学及计数will7101 (CS, Tsinghua)July, 2019

15、19 / 50数学题()()()nn2n22+ · · · +2n 113组合数学及计数will7101 (CS, Tsinghua)July, 201920 / 50数学题()()()nn2n22+ · · · +2n 113()()()()n 1n 1n 1n 12222=+ · · ·0123()()n 1n 122+2n 22n 1=22n1组合数学及计数will7101 (CS, Tsinghua)July, 201920 / 50数学题( )()()()nn + 11n + 22n + m m

16、+ · · · +0组合数学及计数will7101 (CS, Tsinghua)July, 201921 / 50数学题( )()()()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=组合数学及计数will7101 (CS, Tsinghua)July, 201921 / 50目录基本计数原理组合数123 计数技巧例题选讲4组合数学及计数will7101 (CS, Tsinghua)July, 201922 / 50等价替代当法我。具们体需来要讲计，算我一们些构带造特一殊个条双件射的（方一案一数映时射，）可，以将用每一一些种等原价问替题代的的方方案映射为新问题的一种方案，并使答案更容易计算。常用的有捆绑法、插空法、隔板法等。组合数学及计数will7101 (CS, Tsinghua)July, 201923 / 50捆绑法

18、也个称整整体体来法进，行在计计数数。时，如果要求若干物品相邻，则可以将它们作为一组合数学及计数will7101 (CS, Tsinghua)July, 201924 / 50捆绑法也个称整整体体来法进，行在计计数数。时，如果要求若干物品相邻，则可以将它们作为一多例少如种：排AB列C方DE法五。个人要排队，A 和 B 要相邻，C 和 D 要相邻，求有组合数学及计数will7101 (CS, Tsinghua)July, 201924 / 50捆绑法也个称整整体体来法进，行在计计数数。时，如果要求若干物品相邻，则可以将它们作为一多例少如种：排AB列C方DE法五。个人要排队，A 和 B 要相邻，C

19、和 D 要相邻，求有方首案先数将为AB、CD 分别看成一个整体，然后变成 3 个元素的排列问题，然后考虑 AB、CD 内部的相对顺序，共有 4 种情况，3! = 6最终答案为 6 × 4 = 24。组合数学及计数will7101 (CS, Tsinghua)July, 201924 / 50插空法如品果插要入求空若当干中物，品进两行两计不数相。邻，可以先将其他物品放好，然后将这些物组合数学及计数will7101 (CS, Tsinghua)July, 201925 / 50插空法如品果插要入求空若当干中物，品进两行两计不数相。邻，可以先将其他物品放好，然后将这些物例如：ABCDEFG

20、 七个人要排队，ABC 三个人两两不相邻，求方案数。组合数学及计数will7101 (CS, Tsinghua)July, 201925 / 50插空法如品果插要入求空若当干中物，品进两行两计不数相。邻，可以先将其他物品放好，然后将这些物例如：ABCDEFG 七个人要排队，ABC 三个人两两不相邻，求方案数。先将剩下四个人排好，有 4! = 24 种方案；然后将 ABC 三个人插入 5个空当中，有 5 × 4 × 3 = 60 种方案，最终答案为 24 × 60 = 1440。组合数学及计数will7101 (CS, Tsinghua)July, 201925 /

21、 50隔板法将不可区分物品分配问题/不定方程整数解问题转化为插板组合问题。组合数学及计数will7101 (CS, Tsinghua)July, 201926 / 50隔板法将不可区分物品分配问题/不定方程整数解问题转化为插板组合问题。 例案如数：。把 n 个相同的苹果分给 k 个人，要求每个人至少分到一个，求方组合数学及计数will7101 (CS, Tsinghua)July, 201926 / 50隔板法将不可区分物品分配问题/不定方程整数解问题转化为插板组合问题。 例案如数：。把 n 个相同的苹果分给 k 个人，要求每个人至少分到一个，求方我个们人把分这到的n 部个分苹，果而摆每成种一

22、插排板，的从方左案往和右原依来次的插每入一k种分1 配块方隔案板是，一代一表对每应最的终，答案k 为1 块隔板插入 n 1 个空当中（不能插在最左和最右），所以()n 1k 1组合数学及计数will7101 (CS, Tsinghua)July, 201926 / 50隔板法如果改一改原问题，允许有人分到 0 个，那么答案应该怎么改呢？组合数学及计数will7101 (CS, Tsinghua)July, 201927 / 50隔板法如果改一改原问题，允许有人分到 0 个，那么答案应该怎么改呢？刚才的问题可以抽象为数学模型：求方程x1 + x2 + · · · +

23、 xk = n的整数解，满足 xi 1。组合数学及计数will7101 (CS, Tsinghua)July, 201927 / 50隔板法如果改一改原问题，允许有人分到 0 个，那么答案应该怎么改呢？刚才的问题可以抽象为数学模型：求方程x1 + x2 + · · · + xk = n的整数解，满足 xi 1。求如方果程限制改成 xi 0，我们可以设 k 个新变量 yi = xi + 1 1，转化为y1 + y2 + · · · + yk = n + k的整数解，结合刚才的结论，得到答案()n + k 1k 1组合数学及计数will7

24、101 (CS, Tsinghua)July, 201927 / 50改变计数目标如法果转直换接成按容照易题求意的来目计标数。比较困难，可以尝试通过减法、容斥原理等方组合数学及计数will7101 (CS, Tsinghua)July, 201928 / 50改变枚举顺序很的多和时。候直，接计按数照题意做来的做基显本然上只是能：拿在到某暴个力范分围（内x）枚，举我元们素往，往计需算要它安们排一个合适的顺序来计算。组合数学及计数will7101 (CS, Tsinghua)July, 2019 29 / 50改变枚举顺序很的多和时。候直，接计按数照题意做来的做基显本然上只是能：拿在到某暴个力范分

25、围（内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组合数学及计数will7101 (CS, Tsinghua)July, 201929 / 50目录基本计数原理组合数123 计数技巧例题选讲4组合数学及计数will7101 (CS, Tsinghua)July, 201930 / 50数字求和求设 f(x) 为 x 在十进制下的各位数字之和，例如 f(123) = 1

26、 + 2 + 3 = 6，10nf(i)i=0对 109 + 7 取模，n 109。组合数学及计数will7101 (CS, Tsinghua)July, 201931 / 50数字求和 sol朴素做法实际上是先枚举数，再枚举每一位。组合数学及计数will7101 (CS, Tsinghua)July, 201932 / 50数字求和 sol朴素做法实际上是先枚举数，再枚举每一位。考答虑案这的样贡的献顺，序最：后先加枚起举来每。个数码，再计算它出现了多少次，得到它对组合数学及计数will7101 (CS, Tsinghua)July, 201932 / 50数字求和 sol朴素做法实际上是先枚

27、举数，再枚举每一位。考答虑案这的样贡的献顺，序最：后先加枚起举来每。个数码，再计算它出现了多少次，得到它对再来看每个数码出现了多少次：0 10n 相当于每一位都可以任取 0 9码，于是对于每一位上的每个数码，它出现的次数等于其他位任取的方案数 10，然后一共有 n 位，所以每个数码出现的次数为n1n · 10，于是最终答案为n1(1 + 2 + · · · + 9) · n · 10n1组合数学及计数will7101 (CS, Tsinghua)July, 201932 / 50圆盘染色颜一色个不圆同盘，分求为方n 案个数扇。形，用

28、m 种颜色去给染色，要求相邻的两个扇形组合数学及计数will7101 (CS, Tsinghua)July, 201933 / 50圆盘染色 sol的由颜于色形：成了环，不能直接用乘法原理来计算。考虑第 n 块和第 n 2 块组合数学及计数will7101 (CS, Tsinghua)July, 201934 / 50圆盘染色 sol的由颜于色形：成了环，不能直接用乘法原理来计算。考虑第 n 块和第 n 2 块如果颜色相同，则利用整体法看成一块，变为规模为 n 2 的子问题。第 n 1 块可以染 m 1 种颜色。组合数学及计数will7101 (CS, Tsinghua)July, 20193

29、4 / 50圆盘染色 sol的由颜于色形：成了环，不能直接用乘法原理来计算。考虑第 n 块和第 n 2 块题如。果第颜色n 相同块，可则以利染用整m体法看种成颜一色块。，变为规模为 n 2 的子问如果颜色不同1 ，无视第块，变为规模为的子问题。第n 1n 1 1n 1 块可以染 m 2 种颜色。组合数学及计数will7101 (CS, Tsinghua)July, 201934 / 50圆盘染色 sol的由颜于色形：成了环，不能直接用乘法原理来计算。考虑第 n 块和第 n 2 块题如。果第颜色n 相同块，可则以利染用整m体法看种成颜一色块。，变为规模为 n 2 的子问如果颜色不 同1 ，无视第

30、块，变为规模为的子问题。第n 1n 1 1n 1 块可以染 m 2 种颜色。组合数学及计数will7101 (CS, Tsinghua)July, 201934 / 50圆盘染色 sol的由颜于色形：成了环，不能直接用乘法原理来计算。考虑第 n 块和第 n 2 块题如。果第颜色n 相同块，可则以利染用整m体法看种成颜一色块。，变为规模为 n 2 的子问如果颜色不同1 ，无视第块，变为规模为的子问题。第n 1n 1 1n 1 块可以染 m 2 种颜色。综上，得到转移方程f(n) = (m 1)f(n 2) + (m 2)f(n 1)初始条件为 f(1) = 0, f(2) = m(m 1)。组合

31、数学及计数will7101 (CS, Tsinghua)July, 201934 / 50错位排列有 n 个信封和 n 封信，一一对应，求把每封信都装错信封的方案数。组合数学及计数will7101 (CS, Tsinghua)July, 201935 / 50错位排列 sol1利用容斥原理，每都装错，一共为 n 个限制条件，考虑它们补集的交：对于指定的 k 封信，要求它们都装对，方案数为 (n k；而指定 k)!封信有种方案。( )nk组合数学及计数will7101 (CS, Tsinghua)July, 2019 36 / 50错位排列 sol1利用容斥原理，每都装错，一共为 n 个限制条件

32、，考虑它们补集的交：对于指定的 k 封信，要求它们都装对，方案数为 (n k；而指定 k)!封信有种方案。( )nk于是答案为( )nnnn!· k!kk(n k)! =(1)(1)kk=0k=0组合数学及计数will7101 (CS, Tsinghua)July, 201936 / 50错位排列 sol2不也妨可设以为用递推来做。对于 n 号信件，它必然装在 1 n 1 号信封中，1 号（这些情况都是等价的，最后再乘 n 1），再来考虑 1 号信件装在哪里：组合数学及计数will7101 (CS, Tsinghua)July, 201937 / 50错位排列 sol2不也妨可设以为

33、用递推来做。对于 n 号信件，它必然装在 1 n 1 号信封中，1 号（这些情况都是等价的，最后再乘 n 1），再来考虑 1 号信件装在哪里：如果装在 n 号信封中，则剩下 n 2 封信和信封构成一个规模n 2 的子问题；组合数学及计数will7101 (CS, Tsinghua)July, 201937 / 50错位排列 sol2不也妨可设以为用递推来做。对于 n 号信件，它必然装在 1 n 1 号信封中，1 号（这些情况都是等价的，最后再乘 n 1），再来考虑 1 号信件装在哪里：如果装在 n 号信封中，则剩下 n 2 封信和信封构成一个规模n 2 的子问题；号如去果除装，在 k 号信封中

34、（k = n），使用整体法，这种情况等价于将 1n 号信件直接装进 k 号的情况，于是对应了规模为 n 1的子问题。组合数学及计数will7101 (CS, Tsinghua)July, 201937 / 50错位排列 sol2不也妨可设以为用递推来做。对于 n 号信件，它必然装在 1 n 1 号信封中，1 号（这些情况都是等价的，最后再乘 n 1），再来考虑 1 号信件装在哪里：如果装在 n 号信封中，则剩下 n 2 封信和信封构成一个规模n 2 的子问题；号如去果除装，在 k 号信封中（k = n），使用整体法，这种情况等价于将 1n 号信件直接装进 k 号的情况，于是对应了规模为 n 1

35、的子问题。组合数学及计数will7101 (CS, Tsinghua)July, 201937 / 50错位排列 sol2不也妨可设以为用递推来做。对于 n 号信件，它必然装在 1 n 1 号信封中，1 号（这些情况都是等价的，最后再乘 n 1），再来考虑 1 号信件装在哪里：如果装在 n 号信封中，则剩下 n 2 封信和信封构成一个规模n 2 的子问题；号如去果除装，在 k 号信封中（k = n），使用整体法，这种情况等价于将 1n 号信件直接装进 k 号的情况，于是对应了规模为 n 1的子问题。得到递推式p(n) = (n 1) · p(n 1) + p(n 2)初始条件为 p(

36、1) = 0, p(2) = 1。组合数学及计数will7101 (CS, Tsinghua)July, 201937 / 50 SDOI2016 排列计数求度为 n 的排列个数，满足恰好有 m 个数字没有错位。T 组询问，T 5 × 105，n, m 106。答案对 109 + 7 取模。组合数学及计数will7101 (CS, Tsinghua)July, 201938 / 50 SDOI2016 排列计数 sol有做错m位个排没列有。错于位是，答就案相为当于先选出 m 个固定下来，然后剩下 n m 个( )np(n m)m组合数学及计数will7101 (CS, Tsinghu

37、a)July, 201939 / 50 SDOI2016 排列计数 sol有做错m位个排没列有。错于位是，答就案相为当于先选出 m 个固定下来，然后剩下 n m 个们本的题乘主法要逆难元度，在一于个快技速巧求是组利合用数，可以预先处理出 1 n 的阶乘以及它(n 1)!)1 = (n!)1 · n来递推计算逆元，可以做到线性。( )np(n m)m组合数学及计数will7101 (CS, Tsinghua)July, 201939 / 50 HNOI2008 越狱1 . . . n 的 n 个房间，每个房间关押一个犯人，有 m种就监可狱能有发连生续越编狱号，为求可能信仰种其状中态一可

38、种能。发如生果越相狱邻。房间的犯人的宗教相同，有多少组合数学及计数will7101 (CS, Tsinghua)July, 201940 / 50 HNOI2008 越狱 sol减法原理，计算不发生越狱的情况数为 m ·(m 1)，所有情况数为n1，于是答案为 mn m · (m 1)n1。mn组合数学及计数will7101 (CS, Tsinghua)July, 201941 / 50 NOIP2016 组合数问题给出正i整数 k，有 t 组询问，每次求 0 i n, 0 j mini, m 中有多少 (j) 是 k 的倍数。组合数学及计数will7101 (CS, Ts

39、inghua)July, 201942 / 50 NOIP2016 组合数问题 sol由于k 在每组询问中是一样的，求有多少是 k 的倍数，实际上就是求在模 k 意义下有多少个等于零。所以可以通过递推的方式求出 (N, M) 范围内所有的组合数（模 k），然后通过二维前缀和来算出每个 (n) 的答, m案。注进意答：案由。于题目中 j mini, m 而不是 j m，不能将 j > i 的部分算组合数学及计数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求方案数对 109 + 7 取模，n, k 109。组合数学及计数will7101 (CS, Tsinghua)July, 201944 / 50 JSOI2015 子集选取 sol直立接的做，似可乎以非使常用棘乘手法，原观理察，到算一出个n 性=质1 ：时集的合答的案每，个然元后素做对n于次答幂案。是独对n = 1