主要内容

• 加法法则和乘法法则
• 排列与组合
• 二项式定理与组合恒等式
• 多项式定理

• 加法法则
• 乘法法则
• 分类处理与分步处理

问题1：某旅游团从南京到上海，可以乘骑车，也可以乘火车，假定骑车每日有三班，火车每日有2班，那么一天中从南京到上海共有多少种不同的走法？

分类加法计数原理

做一件事，完成他有n类办法，在第一类办法中有m1中不同的方法，在第二类办法中有m2种不同的方法，在第n类办法中有mn中不同的方法，那么完成这件事共有N=m1+m2+…+mn

中不同的方法

分步乘法计数原理

做一件事，完成它需要分成n个步骤，做第一个步骤有m1种不同的方法，做第二个步骤有m2种不同的方法，做第n个步骤有mn种不同的方法，那么完成这件事共有

N= m1xm2x…xmn种不同的方法

例子

从甲地到乙地有2条路可通，从乙地到丙地有3条路可通，从甲地到丁地有4条路可通，才能够丁地到丙地有2条路可通，从甲地经过乙地或丁地到丙地共有——种不同走法

解：由甲到丙有两类不同的走法

第一类：由甲经已去丙，又需要分两步，所以m1=2x3=种不同的走法

第二类：由甲经丁去丙，也需分两步，所以m2=4x2=8种不同的走法所以从甲地到丙地共有n=6+8=14种不同的走法

例1：设A为n元集，问

A上的自反关系有多少个？

A上的对称关系有多少个？

A上的反对称关系有多少个？

A上的函数有多少个？其中双射函数有多少个？

在自反关系矩阵中，主对角线元素都是1，其他位置的元素可以是1,，也可以是2(n^2-n)

考虑对称关系的矩阵，i行j列（i!=j)的元素rij=rji，能够独立选择0或1

的位置有(n^2-n)/2个，加上主对角线的n个位置，总计(n ^2+n)/2个位置，每个位置2种选择，根据乘法法则，构成矩阵的方法数是2 ⁽ⁿ2+n)/2

非主对角线位置分成(n^2-n)/2种，每组元素包含元素rij 和rji，根据反对称的性质， rij与rji的取值有以下三种可能

rij = ,rji=0 rij=0 rji=1 rij=rji=0

所有这些位置元素的选择方法数为3(n^2-n)/2,在考虑到主对角线元素的选取，由乘法法则总方法数为 2^n3( n^2-n)/2

设A={x1,x2,…}任何A上的函数f:A->A具有下述形式

f={<x1,y1,>,<x2,y2>,<x3,y3>…<xn,yn>}

其中每个yi(y=1,2,…,n)有n中可能的选择，根据乘法法则，有n^n个不同的函数，若f是双射的，那么y1确定以后，y2只有n-1中可能的取值，yn只有1一种取值，构成双射函数的方法数是n！

例2：IPV4网址计数

32位地址，网络标识+主机标识

A类：最大网络 B类：中等网络 C：小网络

D：多路广播 E：备用

限制条件：

111111在A类的netid部分无效 hostid部分不允许全0或全1

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MJVCrCiO-1682595643241)(https://pic-1310091761.cos.ap-chengdu.myqcloud.com/img/image-20230427123201058.png)]

选取问题：设n元集合s，从s中选取r各元素，根据是否有序，是否允许重复，将该问题分为四个子类型

定义12.1设S为n元集

从S中有序选取的r个元素称为S的一个r排列，S的不同r排列总数记为P(N,R) R=N的排列是S的全排列

从S中无须选取的r个元素称为S的一个组合，S的不同r组合总数记作C（n，r）

定义1.1设n，r为自然数，规定0!=1,则
< E m p t y   M a t h   B l o c k > <Empty \space Math \space Block> <Empty Math Block>
n!/(n-r)!

c(n,r) = n!/r!(n-r)!

规定0！=1

设n，r为正整数，则
C ( n , r ) = n r C ( n − 1 , r − 1 ) C(n,r)= \frac{n}{r}C(n-1,r-1) C(n,r)=rn​C(n−1,r−1)

C ( n , r ) = C ( n , n − r ) C(n,r)=C(n,n-r) C(n,r)=C(n,n−r)

C ( n , r ) = C ( n − 1 , r − 1 ) + C ( n − 1 , r ) C(n,r) = C(n-1,r-1)+C(n-1,r) C(n,r)=C(n−1,r−1)+C(n−1,r)

定义12.2多重集S={n1a1,n2a2…nk*ak},n=n1+n2+…nk表示S中元素的总数

从S中有序选取的r个元素称为多重集S的一个r排列，r=n的排列称为S 的全排列

从S中无序选取的r个元素称为多重集S的一个r组合

注意：

• 多重集中元素的重复度，0<ni<=正无穷，当ni=正无穷，表示ai重复选取的次数没有限制
• s的子集X={x1a1,x2a2,… xk*ak},其中0<=xi<=ni

定理12.2设S={n1a1,n2a2,…nk*ak}为多重集

1. S的全排列数

n ！ n 1 ! n 2 ! . . . n k ! \frac{n！}{n1!n2!...nk!} n1!n2!...nk!n！​

当r<=ni,i=1，2…k,那么S的r排列数是k^r

r个位置中的每个位置都有k中选法，由乘法法则得到k^r

重要例题

SUCCESS打乱可排出多少个不同的单词

法1 7个位置，放入三个s，2个c，一个u，一个e

乘积法则：C(7,3)C(4,2)C(2,1)C(1,1)

法二 先假定字母各不相同，在排出重复的计数

• 假设字母为S1 ∪C1C2ES2S3其排列数=7!
• 因为C重复，会有2!个排列相同
• 因为S重复，又有3！个排列相同
• 故不同排列数=7!/(3!2!)

在如下棋盘(4x3)中，从左下角走到右上角（只能向右，向上）有多少种走法？

• 无论那种走法，必须7步
• 设0–向右，1–向上
• 每种走法对应1个7位二进制串
• 其中有4个0,3个1

圆排列

从n个元素集合A中任选r个(r<=n)排列且头尾相连（圆排列）

• 1个圆排列每个都可作为开头
  • 1 2 3 4 5 6, 2 3 4 5 6 1,3 4 5 6 1 2,…
• 一个圆排列对应r个普通排列
• 圆排列个数=P(n,r)/r

定理12.3多重集S={n1*a1, n2 xa2,… nk ak} 0<ni<=正无穷,当 r<=ni,S的组合数为N=C(k+r-1,r)

证明 一个r组合为{x1a1,x2a2,…xk*ak}

其中x1+x2+…+xk=r,xi为非负整数，这个不定方程的非负整数解对于下述排列

非负整数解对于下述排列

1…1 x1个

01…1 x2个

01…10 x3个

1…1 xk个

r个 1，k-1个0的全排列数为
N = ( r + k − 1 ) ! / r ! ( k − 1 ) ! N=(r+k-1)!/r!(k-1)! N=(r+k−1)!/r!(k−1)!
C(k+r-1,r)

例题

求x1+x2+x3=11的非负整数解的个数

相当于11个1和2个0的全排列数

C（11+2，2）

例子x1+x2+x3=11的非负整数解个数

约束：x1>=1 x2>=2 x3>=3

• 方法1：元素1先选1个，元素2先选2个，元素3 先选3个
• 已选了六个，剩余五个再从三元素中重复选C(5+2,2)

法二：

令x1=x1’+1 ,x2=x2’+2, x3=x3’+3

问题变为求方程x1’+x2’+x3’=5的非负整数解个数

求 x1+x2+x3=11的非负整数解个数

约束x1>1, x2>2,x3>3

• 等价于x1>=2,x2>=3,x3>=4
• 问题变为求方程x1’+x2’+x3’=非负整数解的个数
• C(2+2,2)

x1+x2+x3=11的非负整数解个数

约束x1<=3

• 第一步，忽略条件想x1<=3（x1仍然是非负整数)C(11+2,2)
• 加入条件x1>=4 方程变为x1’+x2+x3=7 C(9,2)
• 问题的解=1-2

x1+x2+x3=11的非负整数解个数

约束x1<=3 x2>=2,x3>=1

• 忽略条件x1<=3 方程变为x1+x2’+x3’=8 方程变为 x1+x2’+x3’=8
• 加入条件x1>=4 方程变为 x1’+x2’+x3’ = 4
• 问题的解 =1-2

== x1+x2+x3=11的非负整数解个数==

约束:xi<=7

• 第一步忽略条件x<=7结束为C(11+2,2)
• 令Ai代表xi>=8的解的集合，不满足题目条件的解为|A1.∪A2∪A23|利用容斥原理可得3 C(3+2,2)
• 问题的解=1-2

== 不等方程x1+X2+x3<=11的非负整数解个数==

• 引入新变量x4，建立新方程x1+x2+x3+x4=11
• 问题变额外：求新方程的非负整数解个数 C(11+3,3)

例子：不等方程x1+x2+x3>=11的整数解个数

约束：xi<=7

正在为您搜索：不等方程、整数解个数、约束、xi≤7

我们可以先考虑不带约束的情况。设 y i = x i − 1 y_i=x_i-1 yi​=xi​−1，则原式转化为 y 1 + y 2 + y 3 ≥ 8 y_1+y_2+y_3\geq 8 y1​+y2​+y3​≥8，求该不等式的非负整数解个数。根据插板法，我们需要在 8 + 3 − 1 = 10 8+3-1=10 8+3−1=10 个位置中选择 2 2 2 个位置插入隔板，这样就可以将 8 8 8 个苹果分到 3 3 3 个盘子中，其中可能会有空盘子。

因此，不带约束的整数解个数为 C 10 2 = 45 C_{10}^{2}=45 C102​=45。但是，上述方法没有考虑 y i y_i yi​ 的范围限制，因此有些方案是不合法的。接下来，我们需要使用容斥原理来剔除这些不合法的方案。具体而言，我们需要计算 y i > 6 y_i>6 yi​>6 时的方案数，然后用总的方案数减去这些方案数，即可得到带有约束条件的整数解个数。

由于每个 y i y_i yi​ 最大只能取到 6 6 6，因此 y i > 6 y_i>6 yi​>6 的条件等价于 y i ≥ 7 y_i\geq 7 yi​≥7。将 7 7 7 个球放入 3 3 3 个盘子中的方案数为 C 9 2 = 36 C_{9}^{2}=36 C92​=36，但是这些方案中可能存在一个盘子为空的情况，因此需要减去所有空盘子的方案数。将 7 7 7 个球放入 2 2 2 个盘子中的方案数为 C 8 1 = 8 C_{8}^{1}=8 C81​=8，因此将 7 7 7 个球放入 3 3 3 个盘子中、且至少有一个盘子为空的方案数为 3 × 8 − 3 = 21 3\times 8-3=21 3×8−3=21。

最终的结果为 45 − 21 = 24 45-21=24 45−21=24，即不等式 x 1 + x 2 + x 3 ≥ 11 x_1+x_2+x_3\geq 11 x1​+x2​+x3​≥11 在 x i ≤ 7 x_i\leq 7 xi​≤7 的条件下的整数解个数为 24 24 24。

例子3 排列26个字母，使得a与b之间恰有7个自父母，求方法数

解：固定a和b中间选7个字母，有2P(24,7)种方法，将他看作大字母与其余17个字母全排列有18！种，N=2P(24,7)18!

例子 把2n个人分成n组，每组2人，有多少种分法？

解：相当于2n不同的球放到n个相同的盒子，每个盒子两个，方法为
N = 1 n ! C ( 2 n , 2 ) C ( 2 n − 2 , 2 ) . . . C ( 2 , 2 ) N = \frac{1}{n!}C(2n,2)C(2n-2,2)...C(2,2) N=n!1​C(2n,2)C(2n−2,2)...C(2,2)

从S={1，2…，n}中选择k个不相邻的数，有多少种不同的方法？

使用一一对应的思想求解这个问题

a1,a2,…ak k个不相邻的数属于集合{1,2,…,n}

令b1=a1 b2=a2-1 bk = ak-(k-1)

因为a1,a2,…,ak中后一个数至少比前一个大2

所以b1,b2,…bk中后一个数至少比前一个大1

b1 b2 ,…bk为k个允许相邻且互不相等的数，属于集合{1,…,n-(k-1)}

一组b1,b2…bk对应一组a1,a2,…ak取值

因此 N=C(n-k+1,k)

1.求1400的不同的正因子个数是多少？

二项式定理

组合恒等式

设n是正整数，对一切x和y
( x + y ) n = ∑ x k y ( n − k ) (x+y)^n = \sum x^ky^(n-k) (x+y)n=∑xky(n−k)
把10个不同的球放到6个不同的盒子里，允许空盒，且前2个盒子球的总数至多是4，问有多少种放法

根据前两个盒子含球数k对放法分类，其中k=0,1,2,3,4对于给定的k，再分步处理计算放球的方法数

• 从10个球中选放入前两个盒子的k个球，有C(10,k)选法
• 把选好的k个球分到两个盒子里，每个球可以有两种选择，有2^k
• 剩下的n-k个球分到其他4个盒子里有4^n-k种分法
• 根据乘法法则，使得前两个盒子含k个球的放法数是

C（10,k) 2^k 4^n-k

最后使用加法法则对k求和，就得到所求的方法数是