隐藏
组合数学学习笔记 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

组合数学学习笔记

计数原理

加法原理(分类计数原理)

完成一件事有$n$种方法,每种方法有$a_i$种途径,那么完成这件事共有$\sum_i a_i$种不同的方法。

乘法原理(分步计数原理)

完成一件事有$n$个步骤,每个步骤有$a_i$种途径,那么完成这件事共有$\prod_i a_i$种不同的方法。

排列

全排列

将$n$各元素按照不同的顺序排列,设方案数有$f(n)$种($f(0)=1$)。
考虑第一个元素有$n$种选择,故$f(n)=f(n-1)\times n$。

线排列

从$n$个不同的元素中,选出$m$个元素按照一定顺序排列,其方案数称为线排列。
第一个元素有$n$种选择,第二个元素有$n-1$种选择,$\ldots$,第$m$个元素只有$1$种选择。

相异元素可重排列

从$n$个不同元素中,可以重复地选出$m$个元素的排列。
每次选择有$n$种方法,共有$n^m$种方案。

不全相异元素排列

如果在$n$个元素中,有$m$种不同的元素,每种元素有$a_i$个,满足$\sum_i a_i=n$。
$n$个元素的全排列有$n!$种,再除去每一种元素的重复情况。因此答案为:

圆排列

从$n$个不同元素中选取出$m$个元素,不分首尾地排成一个圆圈。
先随便排列,有$A_n^m$种方法,因为是圆排列,重复了$m$次,故答案为:

错排问题

有一个$n$个数的排列$a$,要求任何数$i$都不在位置$i$上,设答案为$D(n)$。
其实是动态规划。

递推公式

假设已有一个排列$a$,显然$a_n\neq n$,不妨设$n=a_i$,考虑数$i$的位置:

  • $i=a_n$:此时$i$与$n$的位置已确定,转化为$n-2$个数的错排问题,情况数为$D(n-2)$。
  • $i\neq a_n$:此时$i$的位置已确定是$n$,转化为$n-1$个数的错排问题,情况数为$D(n-1)$。

以上两种情况$i$有$n-1$种取值,所以$D(n)=(n-1)(D(n-2)+D(n-1))$。

通项公式

通过递推式归纳通项公式,或容斥原理可得:

简化公式

可以简化通项公式为:

然后就可以用$O(\log^2 n)$的方法解决了。

组合

非重组合

从$n$个数中选择$m$个数,不考虑选择数的次序,则总方案数记为$C_n^m$。
我们可以将线排列$A_n^m$看做先从$n$个数中选择$m$个数,再对$m$个元素做全排列。

移项得:

组合数的性质

互补性质

选出$m$个和保留$m$个是等价的。

Pascal公式

考虑最后一个数选与不选。
可以验证组合数排列起来构成杨辉三角。

全方案数

所有的方案数相当于考虑每个数选或不选。

翻转杨辉三角

怎样学习哲学
每一行选一个数,每一行选的数必须比上一行靠右(靠左),问方案数。
画出矩阵发现构成一个翻转的杨辉三角,故用组合数解决。

可重组合

从$n$种无限多的元素中选择$k$个,共有$C_{n+k-1}^k$种方案。
证明:
用$n$个框表示不同的种类,原问题相当于将$k$个元素放入这些框中。
我们可以将$n$个框视为$n-1$个隔板(最前与最后的隔板位置不变,忽略),因此就是隔板与元素随意排列,有$(k+n-1)!$种放法。元素是一样的,隔板也是一样的,都与顺序无关,因此我们需要除掉$k!(n-1)!$种重复情况。
故答案为:

拓展1

可重组合可以理解为不定方程$x_1+x_2+\cdots+x_n=c$的非负整数解个数。
故其可以运用到生成函数中。

拓展2

将$c$个相同的球放在$n$个不同的盒子中,要求每个盒子至少要有一个球的方法总数。
也就是不定方程$x_1+x_2+\cdots+x_n=c$的正整数解个数。

我们可以先将每个盒子都放一个球,故剩下$c-n$个球,转化为非负整数解个数。
故答案为:

组合数的计算

这里提到过所有组合数的计算方法。

一些公式

自然数平方和

证明:

因为有$n(n+1)=\frac{n(n+1)(n+2)-(n-1)n(n+1)}3$。
所以有:

二项式定理

推广

见百度百科
其中牛顿二项式扩充定理可用于证明生成函数的一个结论(用上述可重组合也可证明)

Catalan数

Catalan数的递归定义式为:

另类递推式为:

根据递推关系归纳通项公式:

应用1:凸$n$边形的三角形剖分


我们每次在一个编号不为$1,n$的点中找到一个点$i$,$P_1,P_n,P_i$构成三角形③,剩下了区域①和区域②,可以划归为子问题,故可以得到递推式:

这就是Catalan数列经过平移后得到的数列。

应用2:01排列问题

$n$个$1$和$n$个$0$组成$2$n位的二进制数,要求从左到右扫描,$1$的累计数不小于$0$的累计数,试求满足这条件的数有多少?

不符合要求的数从左向右扫描的时候,必然在某一奇数位$2m+1$位首次出现$m+1$个$0$和$m$个$1$的累计数,此后的$2(n-m)-1$位上有$n-m$个$1$和$n-m-1$个$0$,若将后面$2(n-m)-1$位的$01$互换,可得到一个$n+1$个$0$与$n-1$个$1$组成的排列。
反过来也是对应的。

因此,不符合要求的排列与$n+1$个$0$与$n-1$个$1$组成的排列一一对应,故不符合要求的方案数有$C_{2n}^{n+1}$,故答案为:

Catalan通项公式之一。

应用3:出栈序列

$n$个数按照一定顺序入栈,求不同的出栈序列数目。(本问题可转化为应用2)
设$f(n)$为答案。
设第$n$个元素第$i$个出栈,前面出栈的有$i-1$个元素,后面出栈$n-1$个元素,因此有:

标准Calatan递推公式。

应用4:二叉树形态计数

求$n$个结点能构成不同的二叉树数目。

选定一个结点为根,左子树结点数为$i$,右子树结点数为$n-i-1$,则:

标准Catalan递推公式。

应用5:乘法加括号

对于连乘$a_0\times a_1\times a_2\times\cdots\times a_n$,加括号改变它的运算顺序,问有多少种不同的运算顺序。
将乘号依次作为根当为二叉树处理,转化为应用4。

stirling数

其实stirling数就是两类动态规划,单独称为stirling数。
其中第二类stirling数更重要且应用更广泛。

第一类stirling数

$S_1(n,k)$表示将$n$个不同元素排成$k$个非空循环排列的方案数。

考虑第$n$个元素,可以单独构成一个非空循环排列,有$S_1(n-1,k-1)$种方案。也可以和前$n-1$个元素构成$k$个非空循环排列,第$n$个元素插入到其中一个数的左边,有$(n-1)S_1(n-1,k)$种方案。

第二类stirling数

$S_2(n,k)$表示将$n$个不同元素的集合划分成正好$k$个非空子集的方案数。

考虑第$n$个元素,可以单独构成一个集合,有$S_2(n-1,k-1)$种方案。也可以加入前$n-1$个元素构成的集合,一共有$k$个可加入的集合,方案数为$kS_2(n-1,k)$。

容斥原理

统计多个集合并的大小。
可以先加上所有集合大小,再减去多加的两个集合交的大小,再加上多减的三个集合交的大小$\cdots\cdots$

每一项的符号取决于是几个集合的交。

姥爷们赏瓶冰阔落吧~