组合数学

二项式系数

上升幂和下降幂

定义下降幂.

定义上升幂.

上升幂和下降幂的定义是可以引申到复数域的.

例如我们有加倍公式:.

他们之间存在转换:.

同时存在大小关系:,其中.

二项式系数的定义

考虑令表示从一个大小为的子集中选出大小为的子集的方案数.第一次有个选择,第二次有个选择......第m次有个选择.而由于可能可以选择重复的,但一个排列被重复选择的次数显然是,因此显然有.

如果我们把它的定义拓展到复数域,我们有:

.

值得一提的是,如果我们这么定义,本质上其实是把看作了一个关于的次多项式.

另外根据定义,时,该公式给出.

值得一提的是,为了使二项式系数在面对的时候更加简洁,通常直接定义.

另外不难发现是所有中最大的.事实上我们有Wallis公式:.

基本的二项式恒等式

1. 阶乘展开式:.

证明根据定义是显然的.

2. 对称恒等式:.

根据,时是显然的.而其他情况两边都会给出,因此也是成立的.

3. 吸收恒等式:.

证明根据定义是显然的.

4. 吸收恒等式的变式:.

根据,只需要验证的情况即可,也是显然的.

5. 相伴恒等式:.

证明如下:

问题在于:我们在上述描述中并未提到的范围,但是推导过程要求.不过,我们已经说明了二项式系数是关于的次多项式,因此只需要有个满足这个公式即可.而根据推导过程显然有无限个满足,因此这个公式对也是成立的.

不过事实上,直接用吸收恒等式就可以证明:

6. 加法公式:.

证明可以使用定义,也可以先用的情况给出组合意义,再使用多项式推理法证明.

7. .

证明可以使用组合意义和多项式推理法.

8. 平行求和法:.

我们不妨考虑不断使用加法公式:

,最终下标会减成负数,这样后面的项就全都是了.

也可以考虑组合意义:如果,那么我们考虑从右到左第一个没有被选上的数,假设它是,那么在它右边的数全部选择了,一共是个数,而还需要在左边的中选择个数.

9. 上指标求和法:.

可以组合意义解释:我们不妨假设选的最大数是,接下来就还需要在中选择个.

如果我们将这个公式两边同时乘以,我们可以得到公式:,这也就是有限微积分的公式中的一个.

10. 二项式定理:.

可以使用组合意义证明.

二项式定理有一些有用的特殊情况:

在二项式定理中令即可证明.

在二项式定理中令即可证明,值得一提的是,当的时候这个式子给出,并在其他情况下给出,这个式子是二项式反演的基础.

11. 三项式定理:.

证明与二项式定理类似.值得一提的是,.

12. 多项式定理:.

证明与二项式定理类似.

13. 范德蒙德卷积:.

证明可以使用组合意义和多项式推理法.

另外,这个式子可以直接使用生成函数证明.

14. 范德蒙德卷积的变式:.

有,然后运用范德蒙德卷积即可得到答案.

15. 上指标反转公式:.

根据定义显然.

扩展的二项式恒等式(整数范围内)

1. .

证明如下:

2. .

可以组合意义与多项式推理法证明.

3. .

可以数学归纳证明.

4. .

我们有,两边同时除以,于是我们得到了.

有:

5. .

根据上指标反转公式,这个公式两边都等于.

6. .

可以使用归纳法证明这个公式.

7. .

不妨令左边的值为,我们有:

左右两边满足相同递归式,通过数学归纳法不难证明二者相等.

8. .

考虑,将带入,得到:

9. .

可以数学归纳证明.

10. .

可以数学归纳证明.

拓展的二项式恒等式(实数范围内)

1. .

将加倍公式两边同时除以即可得到这个公式.

2. .

将中令即可得到这个公式.

3. .

即的变形.

首先根据,左边,而考虑到和必有一个是自然数,因此可以直接用范德蒙德卷积的变形.

5. .

直接使用范德蒙德卷积即可证明.

6. .

由和不难推出.

7. .

令,直接做高阶差分即可得到这个式子.

8. .

首先不难发现,.

考虑.

我们有,不难发现即上式.

卡特兰数

卡特兰数表示:长度为的合法括号序列个数.

卡特兰数的前几项为.

接下来,我们通过这个定义来证明以下其他定义方式.

递归定义:.

不妨考虑枚举一个括号序列的第一个断点,则该括号序列应形如.

考虑将其删成和,则一定合法,因为若不合法,那么这里一定不是第一个断点.

通项公式:.

考虑平面直角坐标系,我们将'('认为是向右上走一单位长度,将')'认为是向右下走一单位长度.

那么卡特兰数就相当于从走到不经过第四象限的方案数.

考虑反射容斥,如果只是走到的方案数是.

而如果到达第四象限,说明在这条这线上存在一个点.

考虑将以后的折线以直线为对称轴反转,那么终点到了.

不难发现,任意从走到的方案一定唯一对应了一种从走到的不合法方案.因为从走到一定会经过直线,将后半部分对称后就是其对应方案.而从走到的方案数为.

因而.

而.

递推定义:.

使用一下上一步的通项公式:

f_n=\frac{(2n)!}{n!(n+1)!}\

f_{n-1}=\frac{(2n-2)!}{(n-1)!(n)!}

\end{cases}\

不难发现.整理,得到.

换个记号,设为卡特兰数的第项,卡特兰数有一个著名的结论是次卷积:

我们可以这么理解它:它指的是一个长度为的括号序列,前个必须是左括号的方案数.为啥呢?因为这样这个括号序列必须写成之类的形式,等价于卷积.

那么证明就很简单了,类似反射容斥,有:

Example([HNOI2009]有趣的数列)

首先,如果没有第三条限制,那显然奇数位置和偶数位置互不影响,直接随便选,答案就是.

而有了限制呢,我们还是想随便选然后顺序排起来,但是这次不能排列的时候使奇数位置大于偶数位置,可以发现这就是括号序列需要满足的条件,于是答案就是卡特兰数.

至于处理,这题因为模数不是质数,需要做质因数分解来维护除法.

Example2([23省选10连测day7]b)

给定,对,固定做笛卡尔树的形态计数..

由于是对树的形态计数,其实根本就不在乎每个点具体的取值,只要这个取值有解就行.事实上,容易发现只要满足:

1. 节点的祖先数量不超过个(深度小于等于).

2. 节点的子树大小不超过.

发现合法不太好记,经典补集转化,然后两个不合法情况无关,分别算.

我们考虑直接算出表示的深度为的答案,表示的子树大小为的答案,然后就可以完成这个题.

这两部分怎么算呢?

先看深度:的祖先有两种:一种在序列中在的左边,一种在的右边.我们设前者为,设后者为.这么分类有什么用呢?我们考虑这一段数能放在哪里,它只能是的左儿子,独立于整棵树,因此这一段的答案就是.

记:

注意到这等价于卡特兰数的次卷积,有:

此时的答案自然是,做卷积.

儿子怎么算呢?二叉搜索树有一个经典性质:确定根后每个点插在哪里是固定的.也就是说我们把的子树从原树中删去,然后插入一定会插回原位置,这是一个双射.而子树内随便做,设左子树大小为,右子树大小为,我们有,同样是简单的卷积.

二项式系数的处理

通过恒等式变形求解

Example1

求.

这个式子乘了个系数导致很难处理,一个自然的想法是使用吸收恒等式将消去,然后对后面的式子使用上指标求和.

于是:

不妨令,不难发现我们有:

于是原式.

不过事实上,我们有另一种方式来处理这个等式,我们直接将带入:

Example2

求.

第一反应仍然是使用吸收恒等式,但是注意到和的范围不一样,由于吸收恒等式的范围很松,因此应选择一个范围更松的数吸收,这样才能保证另一个数范围的特殊性,于是有:

Example3

求.

我们有:

Example4

求.

考虑恒等式扩展的二项式恒等式(整数范围内)的,我们有:

注意到如果,则应为.所以有:

Example5

求.

转化为递归式/和式求解

Example1

求.

如果要转化为递归式的话,我们所掌握的只有加法恒等式,但加法恒等式只给出了杨辉三角中相邻两行的关系.但由于的式子中实际上只与有关,我们不妨令,显然有.

而我们有:

也即具有周期性,不难计算前几项答案,最后有.

Example2

求.

考虑设,则有:

整理上式,得到:.

于是我们得到了关于的转移方程,可以矩阵加速.

利用微积分求解

Example

求.

取,则原式.

转化为二维平面

Example1

多次询问给定,,求,.

我们把模型抽象成:在二维平面上,从随机游走到正下方(包含这个点)的概率,容易发现此时向右走了步,总共走了步,然后再向右走一步保证第一次走到了下方.

因为是概率,所以当我们已经确定这个事会发生的时候可以多走几步,不难发现这里的概率等价于走到这条直线时横坐标的概率.枚举一下总共向上走了几步,就得到,注意这里是,因为从一开始钦定了一步,因此映射过来需要多乘个,反映射就要乘个.但是这个式子还是做不了,因为并不满足.我们需要另辟蹊径.

做一下补集转化转化成走到上方的概率,这个概率就等价于.我们考虑暴力预处理出,每次删掉一个后缀的组合数就行.现在的问题在于怎么做.

直接拆组合数,我们有:

Lucas定理

若是质数,则.

或者说,将和在进制下分解,再逐位求组合数并相乘.

证明:

首先,若且,.

而根据二项式定理,.

令,,则.

而,有.

根据二项式定理,即项的系数.

我们可以得出,,那么有.

另外,Lucas定理有一个很重要的推论是:

Example1([CF1770F]Koxia and Sequence)

首先观察样例并思考,可以发现当为偶数时,显然翻转整个序列就可以一一对应(除非翻转后与本身相同,但这种情况下异或值也是),所以异或值为.不然,我们可以翻转,得出答案应该是所有的异或和.

问题在于接下来怎么做,我们考虑把按位或的那个东西容斥掉.现在问题转化为:对于所有,求出满足时,异或和.接下来怎么做呢?我们考虑拆位,若,假设的第位是,然后讨论此时它对答案是否会产生贡献.

我们不难发现,第位贡献是:

这个东西看上去没办法做,但我们突然想到个事:Lucas定理的推论:.

所以原式化简为:

然后呢?不难发现后面那一串是范德蒙德卷积的形式,就可以写成:

扩展Lucas定理

令,那我们只要对于每个求出,然后使用中国剩余定理合并即可.

那现在问题转化为要求,其中.

原式.

现在问题转化为求以及.

注意到:

递归求解即可.

ps:

这样摆式子可能非常难以理解,我们考虑将的所有数全部排成一个宽为的矩阵.

那右边第一项就是把那些的倍数的列拿出来,第二项是那些填满的行,第三项是最后没填满的一行.

斯特林数

第一类斯特林数

:长度为的排列划分成个轮换的方案数.

考虑现在已经将个数分成了若干轮换,现在新加入第个数.这个数要么和其他的数一起组成轮换,要么自己形成自环.

而由于它可以插入前面轮换的任意位置,显然.

特别地,我们定义.

由于所有的排列都由若干置换组成,因此我们有:.

第二类斯特林数

:将个本质不同的物品划分成k个非空集合的方案数.

考虑现在已经放好个物品,正要放入第个物品.那么这个物品要么单独放在一起,要么和其他物品放在一起.显然.

特别地,我们定义.

斯特林数的扩展

如果我们让斯特林数的定义式扩展到整数域,我们可以发现一个性质:.

基本斯特林恒等式

1. .

证明:先考虑前半段,不妨使用数学归纳.若,我们要证

考虑,所以.那么左边即:

至于后半段,由于,所以.

不妨用来代替,我们有:

2. .

3. .

证明:

先考虑前者,由于,所以类似于(1)前半段的推导即可得到,后者同样可以使用下降幂和上升幂的转化来得到.

4. 反转公式:.

证明:

考虑先证明后半部分,将(3)带入(1),得到.

由于这对任意都成立,因此右边除了以外的项系数均为,而的系数为.前半部分是同理的.这个公式是斯特林反演的基础.

5. .

6. .

证明:对于前者,考虑组合意义,将个分为组,也就是先找一部分分成组,再把剩下的分到一组.对于后者,也可以同样考虑组合意义.

补充斯特林恒等式

7. .

8. .

证明:由(5)(6),根据二项式反演可知.

9. .

证明:首先有,对这个式子进行二项式反演即可.

10. .

证明:

考虑组合意义,相当于先把前个分为组,把第个数放到第组.然后剩下个随便放.相当于我们按照每组所放的数的最小值区分每组.由于这么做,第组(最小值最大的那组)在不同的时候最小值是不同的,因此一定不重不漏.

11. .

证明:

先考虑前半部分,首先如果,我们有.这个式子很显然,我们现在有一个长度为的环,想要往里插入第个数有种选择,所以我们有:,数学归纳一下即可.

那么前半部分的组合意义就是:考虑将个数划分成个环,我们先将其中个数划分成个环,剩下个数划分成另一个环.但是这样算显然会算重,所以我们只需要勒令第个数在最后一个环里即可.该证明就显然了.

而由于.因此后半部分也得证.

12. .

13. .

证明:

先考虑前者,我们将个位置分到个集合之后.还剩下个数,剩下个集合.

拿出来这个数,剩下的数刚好够每个集合放一个.最后枚举一下把放在哪里即可.由于每个划分一定存在一段(可能是)单独自己集合的后缀.所以这个递推成立.后者也可以同样证明.

14. .

证明:

考虑,不妨设,相当于将个数分成非空组,然后组内的数要形成若干轮换的方案数.那么知道.

设,那么知道:

显然,数学归纳即可.

15. .

16. ，其中.

证明:考虑(5)(6),对其做一遍斯特林反演即可.

17. .

18. .

证明:先考虑前者,左边即先将个数分为个集合,然后再挑出个集合.那不妨枚举这个集合中是哪些数,然后再进行分配.后者同理.

欧拉数

记表示的排列中满足这条性质的排列个数:存在且只存在个升高,换句话说,存在且只存在个,满足,.不难发现.

考虑在一个的排列中插入,设插入的位置是原本的后面,那么要么原本,要么反之.前者不会改变排列的升高的数量,后者则会增加.另外还有一种情况是插入到了序列最前面.于是我们自然得到:.

特别地,我们令,若,则.

欧拉数与二项式系数

我们有Worpitzky恒等式:

还有另一个恒等式:

剩下的不会了.

伯努利数

定义为第个伯努利数,且满足.

定义.

伯努利数满足公式:.

证明如下:

对使用扰动法,我们有:

接下来使用数学归纳,假设时该公式成立,并假设有,我们只需要证明.

显然,上式成立.

斐波那契数

定义斐波那契数.

斐波那契数的扩展定义

首先根据数学归纳,不难证明卡西尼恒等式:

事实上,如果我们将斐波那契数的递推式改写作:,我们可以在的时候定义斐波那契数,同样也是满足上面的恒等式的,而且我们可以发现:

斐波那契数与数论

如果我们考虑不断使用斐波那契递推式展开,不难发现:

另外,如果我们在上面这个式子中取并使用归纳法,我们又可以得到一个性质:是的倍数,.

再观察这个式子,使用归纳法可以证明,进一步有:.

如果我们推广这个结论,就可以得到一个重要的性质:

如果我们再一次推广这个结论,可以得到马蒂亚舍维奇引理:

这个引理的证明如下:

由于.于是我们有:,也就是.

另外我们有:.

同理,使用归纳法可以证明:.

而,于是.

斐波那契数系

我们如果定义,那么有齐肯多夫定理:

每个正整数都有唯一的表示方式满足:.

首先证明存在性:我们考虑数学归纳,对于一个数n,如果满足,则显然成立,不然,应满足,而的表示已经存在了.另外,由于,因此必定不可能出现选了又选了的情况,存在性得证.

至于唯一性,如果我们不选择而是选择,那么显然接下来无论怎么选,它们的加和都不可能大于等于,因此一定是唯一的.

这样的话,我们可以将一个自然数以斐波那契数的形式表示出来.

斐波那契数的封闭形式

使用生成函数,令.那么不难发现,也就是.

考虑这个形式一定可以分解为的形式,而这两种形式对应的生成函数都很显然.

进行因式分解,如果令,那么可以得到.

另外,由于的影响很小,于是又有.

连项式

连项式多项式定义为:.

通过定义不难发现:.

继续观察式子,会发现它递归的过程相当于枚举是否消掉相邻的一对数.我们考虑用这样一种形式的字符串来表示最后某一项的情况:'.'为还没有消除掉的项,长度为;'-'为已经消除了的两项,长度为.那么就可以表示为一个长度为的字符串,其中若有个'-',有个'.',则有种不同的排列方式.

于是我们有:

另外,这也导出:.

考虑上面的构造过程,不难发现.

于是递归式可以写成:.

进一步地,不断展开后得到:

另外,根据连项式的定义,不难导出.

由这个公式可以推出:.

不断做这个迭代,于是我们可以得到连项式与连分数之间的关系:

另外,这个与数论中的Stern-Brocot树有很大关系,暂略.