组合数学

发表于 2025-06-23 分类于具体数学 Waline：

二项式系数

上升幂和下降幂

定义下降幂$x^{ \underline{ k } } = \prod_{ i = 0 }^{ k - 1 } ( x - i ) = \frac{ x ! }{ ( x - k ) ! }$.

定义上升幂$x^{ \overline{ k } } \prod_{ i = 0 }^{ k - 1 } ( x + i ) = \frac{ ( x + k - 1 ) ! }{ ( x - 1 ) ! }$.

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

例如我们有加倍公式:$r^{ \underline{ k } } ( r - 0 . 5 )^{ \underline{ k } } = \cfrac{ ( 2 r )^{ \underline{ 2 k } } }{ 2^{ 2 k } } , k \in \mathbb{ N }$.

他们之间存在转换:$x^{ \underline{ n } } = ( - 1 )^n ( - x )^{ \overline{ n } }$.

同时存在大小关系:$x^{ \underline{ n } } \leq x^n \leq x^{ \overline{ n } }$,其中$0 \leq n < x$.

二项式系数的定义

考虑令$\binom{ n }{ m }$表示从一个大小为$n$的子集中选出大小为$m$的子集的方案数.第一次有$n$个选择,第二次有$n - 1$个选择……第m次有$n - m + 1$个选择.而由于可能可以选择重复的,但一个排列被重复选择的次数显然是$m !$,因此显然有$\binom{ n }{ m } = \cfrac{ n^{ \underline{ m } } }{ m ! }$.

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

$\binom{ r }{ k } = \begin{cases}\cfrac{ r^{ \underline{ k } } }{ k ! } & k \geq 0 \ 0 & k < 0\end{cases} , r \in \mathbb{ C } , k \in \mathbb{ Z }$.

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

另外根据定义,$r \in \mathbb{ Z } \land r < k$时,该公式给出$0$.

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

另外不难发现$\binom{ 2 n }{ n }$是所有$\binom{ 2 n }{ k }$中最大的.事实上我们有Wallis公式:$\lim_{ n \rightarrow \infty } \frac{ ( \frac{ 2^{ 2 n } }{ \binom{ 2 n }{ n } } )^2 }{ 2 n + 1 } = \frac{ \pi }{ 2 }$.

基本的二项式恒等式

阶乘展开式:$\binom{ n }{ k } = \cfrac{ n ! }{ k ! ( n - k ) ! } , n , k \in \mathbb{ N } , n \geq k \\$.

证明根据定义是显然的.

对称恒等式:$\binom{ n }{ k } = \binom{ n }{ n - k } , n \in \mathbb{ N } , k \in \mathbb{ Z } \\$.

根据$( 1 )$,$0 \leq k \leq n$时是显然的.而其他情况两边都会给出$0$,因此也是成立的.

吸收恒等式:$\binom{ r }{ k } = \cfrac{ r }{ k } \binom{ r - 1 }{ k - 1 } , k \in \mathbb{ Z } \land k \ne 0 \\$.

证明根据定义是显然的.

吸收恒等式的变式:$k \binom{ r }{ k } = r \binom{ r - 1 }{ k - 1 } , k \in \mathbb{ Z } \\$.

根据$( 3 )$,只需要验证$k = 0$的情况即可,也是显然的.

相伴恒等式:$( r - k ) \binom{ r }{ k } = r \binom{ r - 1 }{ k } , k \in \mathbb{ Z } \\$.

证明如下:

$\begin{aligned} ( r - k ) \binom{ r }{ k } & = ( r - k ) \binom{ r }{ r - k } \\ & = r \binom{ r - 1 }{ r - k - 1 } \\ & = r \binom{ r - 1 }{ k } \end{aligned}$

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

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

$\begin{aligned} k \binom{ r }{ k } & = r \binom{ r - 1 }{ k - 1 } \\ ( r - k ) \binom{ r }{ r - k } & = r \binom{ r - 1 }{ r - k - 1 } \\ ( r - k ) \binom{ r }{ k } & = r \binom{ r - 1 }{ k } \end{aligned}$

加法公式:$\binom{ r }{ k } = \binom{ r - 1 }{ k } + \binom{ r - 1 }{ k - 1 } , k \in \mathbb{ Z } \\$.

证明可以使用定义,也可以先用$r \in \mathbb{ N }$的情况给出组合意义,再使用多项式推理法证明.

$\binom{ r }{ m } \binom{ m }{ k } = \binom{ r }{ k } \binom{ r - k }{ m - k } , n , k \in \mathbb{ Z } \\$.

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

平行求和法:$\sum_{ k \leq n } \binom{ r + k }{ k } = \binom{ r + n + 1 }{ n } , n \in \mathbb{ N } \\$.

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

$\binom{ r + n + 1 }{ n } = \binom{ r + n }{ n } + \binom{ r + n }{ n - 1 } = \binom{ r + n }{ n } + \binom{ r + n - 1 }{ n - 1 } + \binom{ r + n - 1 }{ n - 2 } = . . . \\$,最终下标会减成负数,这样后面的项就全都是$0$了.

也可以考虑组合意义:如果$r \in \mathbb{ N }$,那么我们考虑从右到左第一个没有被选上的数,假设它是$r + k + 1$,那么在它右边的数全部选择了,一共是$n - k$个数,而还需要在左边的$r + k$中选择$k$个数.

上指标求和法:$\sum_{ 0 \leq k \leq n } \binom{ k }{ m } = \binom{ n + 1 }{ m + 1 } , n , m \in \mathbb{ N } \\$.

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

如果我们将这个公式两边同时乘以$m !$,我们可以得到公式:$\sum_{ 0 \leq k \leq n } k^{ \underline{ m } } = \cfrac{ ( n + 1 )^{ \underline{ m + 1 } } }{ m + 1 } , n , m \in \mathbb{ N } \\$,这也就是有限微积分的公式中的一个.

二项式定理:$( x + y )^r = \sum_{ k } \binom{ r }{ k } x^k y^{ r - k } , r \in \mathbb{ N } \\$.

可以使用组合意义证明.

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

$\begin{aligned} \sum_{ 0 \leq k \leq n } \binom{ n }{ k } & = 2^n , n \in \mathbb{ N } \\ \end{aligned}$

在二项式定理中令$x = y = 1$即可证明.

$\begin{aligned} \sum_{ 0 \leq k \leq n } ( - 1 )^k \binom{ n }{ k } & = 0^n = [ n = 0 ] , n \in \mathbb{ N } \\ \end{aligned}$

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

三项式定理:$( x + y + z )^n = \sum_{ 0 \leq a , b , c \leq n } [ a + b + c = n ] \cfrac{ n ! }{ a ! b ! c ! } x^a y^b z^c , n \in \mathbb{ N } \\$.

证明与二项式定理类似.值得一提的是,$\cfrac{ n ! }{ a ! b ! c ! } = \binom{ n }{ b + c } \binom{ b + c }{ c }$.

多项式定理:$( \sum_{ i = 1 }^m x_i )^n = \sum_{ \forall i \in [ 1 , m ] , 0 \leq a_i \leq n } [ \sum_{ i = 1 }^m a_i = n ] \cfrac{ n ! }{ \prod_{ i = 1 }^m a_i ! } \prod_{ i = 1 }^m x_i^{ a_i } , n \in \mathbb{ N } \\$.

证明与二项式定理类似.

范德蒙德卷积:$\sum_{ k } \binom{ r }{ m + k } \binom{ s }{ n - k } = \binom{ r + s }{ n + m } , n , m \in \mathbb{ Z } \\$.

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

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

范德蒙德卷积的变式:$\sum_{ k } \binom{ l }{ m + k } \binom{ s }{ n + k } = \binom{ l + s }{ l - m + n } , l \in \mathbb{ N } , n , m \in \mathbb{ Z } \\$.

有$\binom{ l }{ m + k } = \binom{ l }{ l - m - k }$,然后运用范德蒙德卷积即可得到答案.

上指标反转公式:$\binom{ r }{ k } = ( - 1 )^k \binom{ k - r - 1 }{ k } \\$.

根据定义显然.

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

$\sum_{ k \leq m } \binom{ r }{ k } ( - 1 )^k = ( - 1 )^m \binom{ r - 1 }{ m } , m \in \mathbb{ Z } \\$.

证明如下:

$\begin{aligned} \sum_{ k \leq m } \binom{ r }{ k } ( - 1 )^k & = \sum_{ k \leq m } \binom{ k - r - 1 }{ k } \\ & = \binom{ - r + m }{ m } = ( - 1 )^m \binom{ r - 1 }{ m } \end{aligned}$

$\sum_{ - q \leq k \leq l } \binom{ l - k }{ m } \binom{ q + k }{ n } = \binom{ l + q + 1 }{ m + n + 1 } , n , m \in \mathbb{ N } , l + q \geq 0 \\$.

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

$\sum_{ k } \binom{ a + b }{ a + k } \binom{ a + b }{ b + k } ( - 1 )^k = \binom{ a + b }{ a } , a , b \in \mathbb{ N } \\$.

可以数学归纳证明.

$\sum_{ k = 0 }^m \cfrac{ \binom{ m }{ k } }{ \binom{ n }{ k } } = \cfrac{ n + 1 }{ n + 1 - m } , n , m \in \mathbb{ N } , n \geq m \\$.

我们有$\binom{ n }{ m } \binom{ m }{ k } = \binom{ n }{ k } \binom{ n - k }{ m - k } \\$,两边同时除以$\binom{ n }{ m } \binom{ n - k }{ m - k } \\$,于是我们得到了$\cfrac{ \binom{ m }{ k } }{ \binom{ n }{ k } } = \cfrac{ \binom{ n - k }{ m - k } }{ \binom{ n }{ m } } \\$.

有:

$\begin{aligned} \sum_{ k = 0 }^m \cfrac{ \binom{ m }{ k } }{ \binom{ n }{ k } } & = \sum_{ k = 0 }^m \cfrac{ \binom{ n - k }{ m - k } }{ \binom{ n }{ m } } \\ & = \cfrac{ 1 }{ \binom{ n }{ m } } \sum_{ k = 0 }^m \binom{ n - k }{ m - k } \\ & = \cfrac{ 1 }{ \binom{ n }{ m } } \sum_{ k = 0 }^m \binom{ n - m + k }{ k } \\ & = \cfrac{ \binom{ n + 1 }{ m } }{ \binom{ n }{ m } } \\ & = \cfrac{ n + 1 }{ n + 1 - m } \end{aligned}$

$( - 1 )^m \binom{ - n - 1 }{ m } = ( - 1 )^n \binom{ - m - 1 }{ n } , n , m \in \mathbb{ N } \\$.

根据上指标反转公式,这个公式两边都等于$\binom{ n + m }{ m } \\$.

$\sum_{ k \leq m } \binom{ r }{ k } ( \cfrac{ r }{ 2 } - k ) = \cfrac{ m + 1 }{ 2 } \binom{ r }{ m + 1 } , m \in \mathbb{ Z } \\$.

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

$\sum_{ k \leq m } \binom{ m + r }{ k } x^k y^{ m - k } = \sum_{ k \leq m } \binom{ - r }{ k } ( - x )^k ( x + y )^{ m - k } , m \in \mathbb{ Z } \\$.

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

$\begin{aligned} S_m & = \sum_{ k \leq m } \binom{ m + r }{ k } x^k y^{ m - k } = \sum_{ k \leq m } \binom{ m + r - 1 }{ k } x^k y^{ m - k } + \sum_{ k \leq m } \binom{ m + r - 1 }{ k - 1 } x^k y^{ m - k } \\ & = y \sum_{ k < m } \binom{ m - 1 + r }{ k } x^k y^{ m - 1 - k } + \binom{ m + r - 1 }{ m } x^m + x \sum_{ k \leq m } \binom{ m + r - 1 }{ k - 1 } x^{ k - 1 } y^{ m - k } \\ & = ( x + y ) S_{ m - 1 } + \binom{ m + r - 1 }{ m } x^m \\ & = ( x + y ) S_{ m - 1 } + \binom{ r }{ m } ( - x )^m \end{aligned}$

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

$\sum_{ k \leq m } \binom{ m + k }{ k } 2^{ - k } = 2^m , m \in \mathbb{ N } \\$.

考虑$( 7 )$,将$x = y = 1 , r = m + 1$带入,得到:

$\begin{aligned} \sum_{ k \leq m } \binom{ 2 m + 1 }{ k } & = \sum_{ k \leq m } \binom{ m + k }{ k } 2^{ m - k } \\ 2^{ 2 m } & = \sum_{ k \leq m } \binom{ m + k }{ k } 2^{ m - k } \\ 2^m & = \sum_{ k \leq m } \binom{ m + k }{ k } 2^{ - k } \end{aligned}$

$\sum_{ k } \binom{ l }{ m + k } \binom{ s + k }{ n } ( - 1 )^k = ( - 1 )^{ l + m } \binom{ s - m }{ n - l } , l \in \mathbb{ N } , n , m \in \mathbb{ Z } \\$.

可以数学归纳证明.

$\sum_{ k \leq l } \binom{ l - k }{ m } \binom{ s }{ k - n } ( - 1 )^k = ( - 1 )^{ l + m } \binom{ s - m - 1 }{ l - n - m } , l , n , m \in \mathbb{ N } \\$.

可以数学归纳证明.

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

$\binom{ r }{ k } \binom{ r - \cfrac{ 1 }{ 2 } }{ k } = \cfrac{ \binom{ 2 r }{ 2 k } \binom{ 2 k }{ k } }{ 2^{ 2 k } } , k \in \mathbb{ Z } \\$.

将加倍公式两边同时除以$k !^2$即可得到这个公式.

$\binom{ n - \cfrac{ 1 }{ 2 } }{ n } = \cfrac{ \binom{ 2 n }{ n } }{ 2^{ 2 n } } , n \in \mathbb{ Z } \\$.

将$( 1 )$中令$r = k = n$即可得到这个公式.

$\binom{ - \cfrac{ 1 }{ 2 } }{ n } = ( \cfrac{ - 1 }{ 4 } )^n \binom{ 2 n }{ n } , n \in \mathbb{ Z } \\$.

即$( 2 )$的变形.

$\sum_{ k } \binom{ n }{ 2 k } \binom{ 2 k }{ k } 2^{ - 2 k } = \binom{ n - \cfrac{ 1 }{ 2 } }{ \lfloor \cfrac{ n }{ 2 } \rfloor } , n \in \mathbb{ N } \\$

首先根据$( 1 )$,左边$= \sum_{ k } \binom{ \cfrac{ n }{ 2 } }{ k } \binom{ \cfrac{ n - 1 }{ 2 } }{ k } \\$,而考虑到$\cfrac{ n }{ 2 }$和$\cfrac{ n - 1 }{ 2 }$必有一个是自然数,因此可以直接用范德蒙德卷积的变形.

$\sum_{ k } \binom{ - \cfrac{ 1 }{ 2 } }{ k } \binom{ - \cfrac{ 1 }{ 2 } }{ n - k } = ( - 1 )^n , n \in \mathbb{ N } \\$.

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

$\sum_{ k } \binom{ 2 k }{ k } \binom{ 2 n - 2 k }{ n - k } = 4^n , n \in \mathbb{ N } \\$.

由$( 5 )$和$( 3 )$不难推出.

$\sum_{ k } \binom{ n }{ k } \cfrac{ ( - 1 )^k }{ x + k } = x^{ - 1 } \binom{ x + n }{ n }^{ - 1 } , x \notin \{ 0 , - 1 , . . . , - n \} \\$.

令$f ( x ) = ( x - 1 )^{ \underline{ - 1 } }$,直接做高阶差分即可得到这个式子.

$\sum_{ k = 0 }^n \binom{ r }{ k } \binom{ r }{ n - k } ( - 1 )^k = [ n is \mathrm{ even } ] ( - 1 )^{ \cfrac{ n }{ 2 } } \binom{ r }{ \cfrac{ n }{ 2 } } \\$.

首先不难发现,$( 1 - z )^r = \sum_{ k \geq 0 } ( - 1 )^k \binom{ r }{ k } \\$.

考虑$( 1 - z )^r ( 1 + z )^r = ( 1 - z^2 )^r$.

我们有$[ z^n ] ( 1 - z )^r ( 1 + z )^r = [ z^n ] ( 1 - z^2 )^r$,不难发现即上式.

卡特兰数

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

卡特兰数的前几项为$1 , 1 , 2 , 5 , 14 , 42 , 132 \cdots$.

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

递归定义:$f_n = \sum_{ i = 0 }^{ n - 1 } f_i f_{ n - 1 - i }$.

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

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

通项公式:$f_n = \frac{ 1 }{ n + 1 } C_{ 2 n }^n = C_{ 2 n }^n - C_{ 2 n }^{ n - 1 }$.

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

那么卡特兰数就相当于从$( 0 , 0 )$走到$( 2 n , 0 )$不经过第四象限的方案数.

考虑反射容斥,如果只是走到$( 2 n , 0 )$的方案数是$C_{ 2 n }^n$.

而如果到达第四象限,说明在这条这线上存在一个点$( x , - 1 )$.

考虑将$x$以后的折线以直线$y = - 1$为对称轴反转,那么终点到了$( 2 n , - 2 )$.

不难发现,任意从$( 0 , 0 )$走到$( 2 n , - 2 )$的方案一定唯一对应了一种从$( 0 , 0 )$走到$( 2 n , 0 )$的不合法方案.因为从$( 0 , 0 )$走到$( 2 n , - 2 )$一定会经过直线$y = - 1$,将后半部分对称后就是其对应方案.而从$( 0 , 0 )$走到$( 2 n , - 2 )$的方案数为$C_{ 2 n }^{ n - 1 }$.

因而$f_n = C_{ 2 n }^n - C_{ 2 n }^{ n - 1 } \\$.

而$C_{ 2 n }^n - C_{ 2 n }^{ n - 1 } = \frac{ ( 2 n ) ! }{ n ! n ! } - \frac{ ( 2 n ) ! }{ ( n - 1 ) ! ( n + 1 ) ! } = \frac{ ( 2 n ) ! }{ n ! ( n + 1 ) ! } = \frac{ C_{ 2 n }^n }{ n + 1 } \\$.

递推定义:$f_n = \frac{ 4 n - 2 }{ n + 1 } f_{ n - 1 } \\$.

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

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

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

\end{cases}\\

不难发现$f_n = \frac{ ( 2 n - 1 ) ( 2 n ) }{ n ( n + 1 ) } f_{ n - 1 } \\$.整理,得到$f_n = \frac{ 4 n - 2 }{ n + 1 } f_{ n - 1 } \\$.

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

$C^{ ( k ) }_n = \sum_{ \sum_{ j = 1 }^k a_j = n } \prod C_{ a_i } = \frac{ k }{ n + k } \binom{ 2 n + k - 1 }{ n }$

我们可以这么理解它:它指的是一个长度为$n + k - 1$的括号序列,前$k - 1$个必须是左括号的方案数.为啥呢?因为这样这个括号序列必须写成$( ( ( A ) B ) C ) D$之类的形式,等价于卷积.

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

$\begin{aligned} C^{ ( k ) }_n & = \binom{ 2 n + k - 1 }{ n } - \binom{ 2 n + k - 1 }{ n - 1 } \\ & = \frac{ k }{ n + k } \binom{ 2 n + k - 1 }{ n } \end{aligned}$

Example([HNOI2009]有趣的数列)

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

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

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

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

给定$x , n$,对$y \in [ 1 , n ]$,固定$p_x = y$做笛卡尔树的形态计数.$n \leq 5 \times 10^5$.

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

$x$节点的祖先数量不超过$y - 1$个(深度小于等于$y$).
$x$节点的子树大小不超过$n - y + 1$.

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

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

这两部分怎么算呢?

先看深度:$x$的祖先有两种:一种在序列中在$x$的左边,一种在$x$的右边.我们设前者为$0 = l_0 < l_1 < l_2 < \cdots l_p < l_{ p + 1 } = x$,设后者为$n + 1 = r_0 > r_1 > r_2 > \cdots > r_{ q } > r_{ q + 1 } = x$.这么分类有什么用呢?我们考虑$( l_{ i - 1 } , l_{ i } )$这一段数能放在哪里,它只能是$l_{ i }$的左儿子,独立于整棵树,因此这一段的答案就是$C_{ l_i - l_{ i - 1 } - 1 }$.

记:

$\begin{aligned} L_p & = \sum_{ l } \prod_{ i = 1 }^{ p + 1 } C_{ l_i - l_{ i - 1 } - 1 } \\ R_q & = \sum_{ r } \prod_{ i = 1 }^{ q + 1 } C_{ r_{ i - 1 } - r_i - 1 } \\ \end{aligned}$

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

$\begin{aligned} L_p & = C_{ x - p - 1 }^{ ( p + 1 ) } \\ R_q & = C^{ ( q + 1 ) }_{ n - x - q } \\ \end{aligned}$

此时的答案自然是$f_{ p + q + 1 } = L_p R_q \binom{ p + q }{ q }$,做卷积.

儿子怎么算呢?二叉搜索树有一个经典性质:确定根后每个点插在哪里是固定的.也就是说我们把$x$的子树从原树中删去,然后插入$x$一定会插回原位置,这是一个双射.而子树内随便做,设左子树大小为$p$,右子树大小为$q$,我们有$g_{ p + q + 1 } = C_p C_q C_{ n - ( p + q + 1 ) } = C_{ n - 1 }^{ ( 3 ) }$,同样是简单的卷积.

二项式系数的处理

通过恒等式变形求解

Example1

求$\sum_{ k = 0 }^n k \binom{ m - k - 1 }{ m - n - 1 } , n , m \in \mathbb{ N } \land m > n \\$.

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

于是:

$\begin{aligned} \sum_{ k = 0 }^n k \binom{ m - k - 1 }{ m - n - 1 } & = \sum_{ k = 0 }^n m \binom{ m - k - 1 }{ m - n - 1 } - \sum_{ k = 0 }^n ( m - k ) \binom{ m - k - 1 }{ m - n - 1 } \\ & = m \sum_{ k = 0 }^{ m - 1 } \binom{ m - k - 1 }{ m - n - 1 } - ( m - n ) \sum_{ k = 0 }^m \binom{ m - k }{ m - n } \end{aligned}$

不妨令$S_m = \sum_{ k = 0 }^m \binom{ m - k }{ m - n } \\$,不难发现我们有:

$S_m = \sum_{ k = 0 }^m \binom{ k }{ m - n } = \binom{ m + 1 }{ m - n + 1 }$

于是原式$= mS_{ m - 1 } - ( m - n ) S_m = \cfrac{ n }{ m - n + 1 } \binom{ m }{ m - n } \\$.

不过事实上,我们有另一种方式来处理这个等式,我们直接将$k = \binom{ k }{ 1 }$带入:

$\begin{aligned} \sum_{ k = 0 }^n k \binom{ m - k - 1 }{ m - n - 1 } & = \sum_{ k = 0 }^n \binom{ k }{ 1 } \binom{ m - k - 1 }{ m - n - 1 } \\ & = \binom{ m }{ m - n + 1 } \\ & = \cfrac{ n }{ m - n + 1 } \binom{ m }{ m - n } \end{aligned}$

Example2

求$\sum_{ k } k \binom{ n }{ k } \binom{ s }{ k } , n \in \mathbb{ N } \\$.

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

$\begin{aligned} \sum_{ k } k \binom{ n }{ k } \binom{ s }{ k } & = s \sum_{ k } \binom{ n }{ k } \binom{ s - 1 }{ k - 1 } \\ & = s \binom{ n + s - 1 }{ n - 1 } \end{aligned}$

Example3

求$\sum_{ 0 \leq k } \binom{ n + k }{ 2 k } \binom{ 2 k }{ k } \cfrac{ ( - 1 )^k }{ k + 1 } , n \in \mathbb{ N } \\$.

我们有:

$\begin{aligned} \sum_{ 0 \leq k } \binom{ n + k }{ 2 k } \binom{ 2 k }{ k } \cfrac{ ( - 1 )^k }{ k + 1 } & = \sum_{ 0 \leq k } \binom{ n + k }{ k } \binom{ n }{ k } \cfrac{ ( - 1 )^k }{ k + 1 } , n \in \mathbb{ N } \\ & = \cfrac{ 1 }{ n + 1 } \sum_{ 0 \leq k } \binom{ n + k }{ k } \binom{ n + 1 }{ k + 1 }{ ( - 1 )^k } \\ & = \cfrac{ 1 }{ n + 1 } \sum_{ 0 \leq k } \binom{ - n - 1 }{ k } \binom{ n + 1 }{ k + 1 } \\ & = \cfrac{ 1 }{ n + 1 } \binom{ 0 }{ n } \\ & = [ n = 0 ] \end{aligned}$

Example4

求$\sum_{ k \geq 0 } \binom{ n + k }{ m + 2 k } \binom{ 2 k }{ k } \cfrac{ ( - 1 )^k }{ k + 1 } , n , m \in \mathbb{ N_+ } \\$.

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

$\begin{aligned} \sum_{ k \geq 0 } \binom{ n + k }{ m + 2 k } \binom{ 2 k }{ k } \cfrac{ ( - 1 )^k }{ k + 1 } & = \sum_{ k \geq 0 } \sum_{ 0 \leq j \leq n + k - 1 } \binom{ n + k - 1 - j }{ 2 k } \binom{ j }{ m - 1 } \binom{ 2 k }{ k } \cfrac{ ( - 1 )^k }{ k + 1 } \\ & = \sum_{ 0 \leq j \leq n - 1 } \binom{ j }{ m - 1 } \sum_{ j + 1 - n \leq k , 0 \leq k } \binom{ n + k - 1 - j }{ 2 k } \binom{ 2 k }{ k } \cfrac{ ( - 1 )^k }{ k + 1 } \end{aligned}$

注意到如果$j + 1 - n \geq 0$,则$\binom{ n + k - 1 - j }{ 2 k } \\$应为$0$.所以有:

$\begin{aligned} & \sum_{ 0 \leq j \leq n - 1 } \binom{ j }{ m - 1 } \sum_{ j + 1 - n \leq k , 0 \leq k } \binom{ n + k - 1 - j }{ 2 k } \binom{ 2 k }{ k } \cfrac{ ( - 1 )^k }{ k + 1 } \\ = & \sum_{ 0 \leq j < n } \binom{ j }{ m - 1 } [ n - 1 - j = 0 ] = \binom{ n - 1 }{ m - 1 } \end{aligned}$

Example5

求$\sum_{ k = 0 }^n ( C_n^k )^2$.

$\sum_{ k = 0 }^n ( C_n^k )^2 = \sum_{ k = 0 }^n C_{ n }^k \times C_{ n }^{ n - k } = C_n^{ 2 n }$

转化为递归式/和式求解

Example1

求$Q_n = \sum_{ k \leq 2^n } \binom{ 2^n - k }{ k } ( - 1 )^k , n \in \mathbb{ N } \\$.

如果要转化为递归式的话,我们所掌握的只有加法恒等式,但加法恒等式只给出了杨辉三角中相邻两行的关系.但由于$Q_n$的式子中实际上只与$2^n$有关,我们不妨令$R_n = \sum_{ k \leq n } \binom{ n - k }{ k } ( - 1 )^k \\$,显然有$Q_n = R_{ 2^n }$.

而我们有:

$\begin{aligned} R_n & = \sum_{ k \leq n } \binom{ n - 1 - k }{ k } ( - 1 )^k + \sum_{ k \leq n } \binom{ n - 1 - k }{ k - 1 } ( - 1 )^k \\ & = \sum_{ k \leq n } \binom{ n - 1 - k }{ k } ( - 1 )^k + \sum_{ k \leq n - 1 } \binom{ n - k - 2 }{ k } ( - 1 )^{ k + 1 } \\ & = \sum_{ k \leq n - 1 } \binom{ n - 1 - k }{ k } ( - 1 )^k + \binom{ - 1 }{ n } ( - 1 )^n - ( \sum_{ k \leq n - 2 } \binom{ n - 2 - k }{ k } ( - 1 )^k + \binom{ - 1 }{ n - 1 } ( - 1 )^{ n - 1 } ) \\ & = \sum_{ k \leq n - 1 } \binom{ n - 1 - k }{ k } ( - 1 )^k - \sum_{ k \leq n - 1 } \binom{ n - 2 - k }{ k } ( - 1 )^k \\ & = R_{ n - 1 } - R_{ n - 2 } \\ & = R_{ n - 2 } - R_{ n - 3 } - R_{ n - 2 } \\ & = - R_{ n - 3 } \\ & = R_{ n - 6 } \end{aligned}$

也即$R_n$具有周期性,不难计算前几项答案,最后有$Q_n \begin{cases}1 & n = 0 \ 0 & n is \mathrm{ odd } \ - 1 & n > 0 \land n is \mathrm{ even }\end{cases}$.

Example2

求$( \sum^{ + \infty }_{ i = 0 } C^{ ik + r }_{ nk } ) \mod p$.

考虑设$f ( n , r ) = \sum^{ + \infty }_{ i = 0 } C^{ ik + r }_{ nk } \\$,则有:

$\begin{aligned} f ( n , r ) & = \sum^{ + \infty }_{ i = 0 } C^{ ik + r }_{ nk } \\ & = \sum_{ i = 0 }^{ + \infty } \sum_{ j = 0 }^k C_{ nk - k }^{ ik + r - j } \times C_k^j \\ & = \sum^k_{ j = 0 } C_k^j \sum_{ i = 0 }^{ + \infty } C_{ nk - k }^{ ik + r - j } \\ & = \sum_{ j = 0 }^k C_k^j f ( n - 1 , r - j ) \\ \end{aligned}$

整理上式,得到:$f ( n , r ) = \sum_{ j = 0 }^k C_k^j f ( n - 1 , r - j ) \\$.

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

利用微积分求解

Example

求$\sum_{ k = 1 }^n k^2 C_n^k$.

$\begin{aligned} ( ( 1 + x )^n ) & = ( \sum_{ k = 0 }^n C_n^k x^{ k } ) \\ ( ( 1 + x )^n ) ' & = ( \sum_{ k = 0 }^n C_n^k x^{ k } ) ' \\ n ( 1 + x )^{ n - 1 } & = \sum_{ k = 0 }^n kC_n^k x^{ k - 1 } \\ nx ( 1 + x )^{ n - 1 } & = \sum_{ k = 0 }^n kC_n^k x^{ k } \\ ( nx ( 1 + x )^{ n - 1 } ) ' & = ( \sum_{ k = 0 }^n kC_n^k x^{ k } ) ' \\ n ( ( 1 + x )^{ n - 1 } + ( n - 1 ) x ( 1 + x )^{ n - 2 } ) & = \sum_{ k = 0 }^n k^2 C_n^k x^{ k - 1 } \\ \end{aligned}$

取$x = 1$,则原式$= n ( n + 1 ) 2^{ n - 2 }$.

转化为二维平面

Example1

多次询问给定$k , r$,$\sum k \leq 2 n , r < 2 n - k$,求$\sum_{ i = 0 }^{ r } \frac{ 1 }{ 2^i } \binom{ i }{ n - k }$,.

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

因为是概率,所以当我们已经确定这个事会发生的时候可以多走几步,不难发现这里的概率等价于走到$x + y = r + 1$这条直线时横坐标$\geq n - k + 1$的概率.枚举一下总共向上走了几步,就得到$\frac{ 1 }{ 2^{ r } } \sum_{ j = 0 }^{ r - n + k } \binom{ r + 1 }{ j }$,注意这里是$\frac{ 1 }{ 2^r }$,因为从一开始钦定了一步,因此映射过来需要多乘个$\frac{ 1 }{ 2 }$,反映射就要乘个$2$.但是这个式子还是做不了,因为$r$并不满足$\sum r \leq 2 n$.我们需要另辟蹊径.

做一下补集转化转化成走到上方的概率,这个概率就等价于$1 - \frac{ 1 }{ 2^{ r } } \sum_{ i = 0 }^{ n - k } \binom{ r + 1 }{ i }$.我们考虑暴力预处理出$f_r = \sum_{ i = 0 }^{ n } \binom{ r }{ i }$,每次删掉一个后缀的组合数就行.现在的问题在于$f$怎么做.

直接拆组合数,我们有:

$\begin{aligned} f_r & = \sum_{ i = 0 }^n \binom{ r }{ i } \\ & = \sum_{ i = 0 }^n \binom{ r - 1 }{ i - 1 } + \sum_{ i = 0 }^n \binom{ r - 1 }{ i } \\ & = 2 \sum_{ i = 0 }^n \binom{ r - 1 }{ i } - \binom{ r - 1 }{ n } \\ & = 2 f_{ r - 1 } - \binom{ r - 1 }{ n } \end{aligned}$

Lucas定理

若$p$是质数,则$C_n^m \mod p = C_{ n \mod p }^{ m \mod p } \times C_{ \lfloor \frac{ n }{ p } \rfloor }^{ \lfloor \frac{ m }{ p } \rfloor } \mod p \\$.

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

证明:

首先,若$i \ne 0$且$i \ne p$,$C_{ p }^i \equiv \frac{ p }{ i } C_{ p - 1 }^{ i - 1 } \equiv 0 ( \mod p ) \\$.

而根据二项式定理,$( 1 + x )^p \equiv \sum_{ i = 0 }^p C_{ p }^i x^i = 1 + x^p ( \mod p ) \\$.

令$n = k_1 p + b_1$,$m = k_2 p + b_2$,则$( 1 + x )^n = ( 1 + x )^{ k_1 p } ( 1 + x )^{ b_1 } \\$.

而$( 1 + x )^{ k_1 p } \equiv ( 1 + x^p )^{ k_1 } ( \mod p ) \\$,有$( 1 + x )^n \equiv ( 1 + x^p )^{ k_1 } ( 1 + x )^{ b_1 } \\$.

根据二项式定理,$C_n^m \bmod p$即$x^m$项的系数.

我们可以得出,$C_n^m x^m \equiv C_{ k_1 }^{ k_2 } x^{ k_2 p } C_{ b 1 }^{ b_2 } x^{ b_2 } \pmod{ p } \\$,那么有$C_a^b \equiv C_{ k_1 }^{ k_2 } C_{ b_1 }^{ b_2 } \pmod{ p } \\$.

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

$\binom{ n }{ m } \equiv [ m \subseteq n ] \pmod{ 2 }$

Example1([CF1770F]Koxia and Sequence)

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

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

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

$[ 2^k \subseteq y ' ] \bigoplus_{ \sum a = x } [ 2^k \subseteq a_1 ] \prod_{ i = 1 }^n [ a_i \subseteq y ' ]$

这个东西看上去没办法做,但我们突然想到个事:Lucas定理的推论:$[ x \subseteq y ] \equiv \binom{ y }{ x } \pmod{ 2 }$.

所以原式化简为:

$\begin{aligned} & \binom{ y ' }{ 2^k } \sum_{ \sum a = x } \binom{ a_1 }{ 2^k } \prod_{ i = 1 }^n \binom{ y ' }{ a_i } \pmod{ 2 } \\ = & \binom{ y ' }{ 2^k } \sum_{ a_1 } \binom{ y ' - 2^k }{ a_1 - 2^k } \sum_{ \sum a = x - a_1 } \prod_{ i = 2 }^n \binom{ y ' }{ a_i } \pmod{ 2 } \\ \end{aligned}$

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

$\begin{aligned} & \binom{ y ' }{ 2^k } \sum_{ a_1 } \binom{ y ' - 2^k }{ a_1 - 2^k } \binom{ ( n - 1 ) y ' }{ x - a_1 } \pmod{ 2 } \\ = & \binom{ y ' }{ 2^k } \binom{ ny ' - 2^k }{ x - 2^k } \pmod{ 2 } \\ = & [ 2^k \subseteq y ' ] [ ( x - 2^k ) \subseteq ( ny ' - 2^k ) ] \end{aligned}$

扩展Lucas定理

令$p = \prod p_i^{ e_i }$,那我们只要对于每个$i$求出$C_n^m \mod p_i^{ e_i }$,然后使用中国剩余定理合并即可.

那现在问题转化为要求$C_n^m \mod p^k$,其中$p \in \mathrm{ prime }$.

原式$= \frac{ n ! }{ m ! ( n - m ) ! } \mod p^k = \frac{ \frac{ n ! }{ p^x } }{ \frac{ m ! }{ p^y } \frac{ ( n - m ) ! }{ p^z } } p^{ x - y - z } \mod p^k \\$.

现在问题转化为求$\frac{ n ! }{ p^x } \mod p^k 以及 p^x \\$.

注意到:

$\begin{aligned} n ! & = \prod_{ i = 1 } i \\ & = ( \prod_{ i = wp , w \in \mathbb{ Z } } i ) ( \prod_{ i \ne wp , w \in \mathbb{ Z } } i ) \\ & = p^{ \lfloor n p \rfloor } ( \lfloor n p \rfloor ! ) ( \prod_{ i \ne wp , w \in \mathbb{ Z } } i ) \\ & \equiv p^{ \lfloor \frac{ n }{ p } \rfloor } ( \lfloor \frac{ n }{ p } \rfloor ! ) ( \prod_{ i = 1 , i \ne wp , w \in \mathbb{ Z } }^{ p^k } i )^{ \lfloor \frac{ n }{ p^k } \rfloor } ( \prod^{ n \ \bmod{ p^k } }_{ i = p^k \lfloor \frac{ n }{ p^k } \rfloor , i \ne wp , w \in \mathbb{ Z } } i ) ( \mod p^k ) \end{aligned}$

递归求解即可.

ps:

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

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

斯特林数

第一类斯特林数

$n \brack k \\$:长度为$n$的排列划分成$k$个轮换的方案数.

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

而由于它可以插入前面轮换的任意位置,显然$\left [ \begin{array}{ c } n \ k\end{array} \right ] = ( n - 1 ) \left [ \begin{array}{ c } n - 1 \ k\end{array} \right ] + \left [ \begin{array}{ c } n - 1 \ k - 1\end{array} \right ] \\$.

特别地,我们定义$\left [ \begin{array}{ c } 0 \ k\end{array} \right ] = [ k = 0 ] \\$.

由于所有的排列都由若干置换组成,因此我们有:$\sum_{ k = 0 }^n \left [ \begin{array}{ c } n \ k\end{array} \right ] = n !$.

第二类斯特林数

$\left \{ \begin{array}{ c } n \ k\end{array} \right \}$:将$n$个本质不同的物品划分成k个非空集合的方案数.

考虑现在已经放好$n - 1$个物品,正要放入第$n$个物品.那么这个物品要么单独放在一起,要么和其他物品放在一起.显然$\left \{ \begin{array}{ c } n \ k\end{array} \right \} = k \left \{ \begin{array}{ c } n - 1 \ k\end{array} \right \} + \left \{ \begin{array}{ c } n - 1 \ k - 1\end{array} \right \} \\$.

特别地,我们定义$\left \{ \begin{array}{ c } 0 \ k\end{array} \right \} = [ k = 0 ] \\$.

斯特林数的扩展

如果我们让斯特林数的定义式扩展到整数域,我们可以发现一个性质:${ n \brack m } ={ - m \brace - n } \\$.

基本斯特林恒等式

$x^n = \sum_{ k = 0 }^n \left \{ \begin{array}{ c } n \ k\end{array} \right \} x^{ \underline{ k } } = \sum_{ k = 0 }^n \left \{ \begin{array}{ c } n \ k\end{array} \right \} ( - 1 )^{ n - k } x^{ \overline{ k } } \\$.

证明:先考虑前半段,不妨使用数学归纳.若$x^{ n - 1 } = \sum_{ k = 0 }^{ n - 1 } \left \{ \begin{array}{ c } n - 1 \ k\end{array} \right \} x^{ \underline{ k } } \\$,我们要证

$\begin{aligned} x \sum_{ k = 0 }^{ n - 1 } \left \{ \begin{array} { c } n - 1 \\ k \end{array} \right \} x^{ \underline{ k } } & = \sum_{ k = 0 }^{ n } \left \{ \begin{array} { c } n \\ k \end{array} \right \} x^{ \underline{ k } } \\ \end{aligned}$

考虑$( x - k ) x^{ \underline{ k } } = x^{ \underline{ k + 1 } }$,所以$x \cdot x^{ \underline{ k } } = x^{ \underline{ k + 1 } } + kx^{ \underline{ k } } \\$.那么左边即:

$\begin{aligned} & \sum_{ k = 0 }^{ n - 1 } \left \{ \begin{array} { c } n - 1 \\ k \end{array} \right \} x^{ \underline{ k + 1 } } + \sum_{ k = 0 }^{ n - 1 } \left \{ \begin{array} { c } n - 1 \\ k \end{array} \right \} kx^{ \underline{ k } } \\ = & \sum_{ k = 1 }^{ n } \left \{ \begin{array} { c } n - 1 \\ k - 1 \end{array} \right \} x^{ \underline{ k } } + \sum_{ k = 1 }^{ n } \left \{ \begin{array} { c } n - 1 \\ k \end{array} \right \} kx^{ \underline{ k } } \\ = & \sum_{ k = 0 }^n \left \{ \begin{array} { c } n \\ k \end{array} \right \} x^{ \underline{ k } } \\ \\ \end{aligned}$

至于后半段,由于$x^{ \underline{ n } } = ( - 1 )^n ( - x )^{ \overline{ n } } \\$,所以$x^n = \sum_{ k = 0 }^n \left \{ \begin{array}{ c } n \ k\end{array} \right \} ( - 1 )^k ( - x )^{ \overline{ k } } \\$.

不妨用$x$来代替$- x$,我们有:

$\begin{aligned} ( - x )^n & = \sum_{ k = 0 }^n \left \{ \begin{array} { c } n \\ k \end{array} \right \} ( - 1 )^k ( x )^{ \overline{ k } } \\ x^n & = \sum_{ k = 0 }^n \left \{ \begin{array} { c } n \\ k \end{array} \right \} ( - 1 )^{ n - k } x^{ \overline{ k } } \end{aligned}$

$x^{ \overline{ n } } = \sum_{ k = 0 }^n \left [ \begin{array}{ c } n \ k\end{array} \right ] x^k \\$.
$x^{ \underline{ n } } = \sum_{ k = 0 }^n \left [ \begin{array}{ c } n \ k\end{array} \right ] ( - 1 )^{ n - k } x^k \\$.

证明:

先考虑前者,由于$( x + n - 1 ) x^k = x^{ k + 1 } + ( n - 1 ) x^k \\$,所以类似于(1)前半段的推导即可得到,后者同样可以使用下降幂和上升幂的转化来得到.

反转公式:$\sum_{ k = 0 }^n \left [ \begin{array}{ c } n \ k\end{array} \right ] \left \{ \begin{array}{ c } k \ m\end{array} \right \} ( - 1 )^{ n - k } = \sum_{ k = 0 }^n \left \{ \begin{array}{ c } n \ k\end{array} \right \} \left [ \begin{array}{ c } k \ m\end{array} \right ] ( - 1 )^{ n - k } = [ m = n ] \\$.

证明:

考虑先证明后半部分,将(3)带入(1),得到$x^n = \sum_{ k = 0 }^n \left \{ \begin{array}{ c } n \ k\end{array} \right \} x^{ \underline{ k } } = \sum_{ k = 0 }^n \sum_{ m = 0 }^k \left \{ \begin{array}{ c } n \ k\end{array} \right \} \left [ \begin{array}{ c } k \ m\end{array} \right ] ( - 1 )^{ n - k } x^m \\$.

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

$\left \{ \begin{array}{ c } n + 1 \ m + 1\end{array} \right \} = \sum_{ k = m }^n \left ( \begin{array}{ c } n \ k\end{array} \right ) \left \{ \begin{array}{ c } k \ m\end{array} \right \} \\$.
$\left [ \begin{array}{ c } n + 1 \ m + 1\end{array} \right ] = \sum_{ k = m }^n \left ( \begin{array}{ c } n \ k\end{array} \right ) \left [ \begin{array}{ c } k \ m\end{array} \right ] \\$.

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

补充斯特林恒等式

$\left \{ \begin{array}{ c } n \ m\end{array} \right \} = \sum_{ k = m }^n \left ( \begin{array}{ c } n \ k\end{array} \right ) \left \{ \begin{array}{ c } k + 1 \ m + 1\end{array} \right \} ( - 1 )^{ n - k } \\$.
$\left [ \begin{array}{ c } n \ m\end{array} \right ] = \sum_{ k = m }^n \left ( \begin{array}{ c } n \ k\end{array} \right ) \left [ \begin{array}{ c } k + 1 \ m + 1\end{array} \right ] ( - 1 )^{ n - k } \\$.

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

$m ! \left \{ \begin{array}{ c } n \ m\end{array} \right \} = \sum_{ k = 0 }^m C_m^k k^n ( - 1 )^{ m - k } \\$.

证明:首先有$m^n = \sum_{ k = 0 }^m m^{ \underline{ k } } \left \{ \begin{array}{ c } m \ k\end{array} \right \} = \sum_{ k = 0 }^m k ! C_m^k \left \{ \begin{array}{ c } m \ k\end{array} \right \} \\$,对这个式子进行二项式反演即可.

$\left \{ \begin{array}{ c } n + 1 \ m + 1\end{array} \right \} = \sum_{ k = 0 }^n \left \{ \begin{array}{ c } k \ m\end{array} \right \} ( m + 1 )^{ n - k } \\$.

证明:

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

$\left [ \begin{array}{ c } n + 1 \ m + 1\end{array} \right ] = \sum_{ k = 0 }^n \left [ \begin{array}{ c } k \ m\end{array} \right ] C_{ n }^k ( n - k ) ! = n ! \sum_{ k = 0 }^n \frac{ \left [ \begin{array}{ c } k \ m\end{array} \right ] }{ k ! } \\$.

证明:

先考虑前半部分,首先如果$n > 0$,我们有$\left [ \begin{array}{ c } n \ 1\end{array} \right ] = ( n - 1 ) ! \\$.这个式子很显然,我们现在有一个长度为$n - 1$的环,想要往里插入第$n$个数有$n - 1$种选择,所以我们有:$\left [ \begin{array}{ c } n \ 1\end{array} \right ] = \left [ \begin{array}{ c } n - 1 \ 1\end{array} \right ] ( n - 1 ) \\$,数学归纳一下即可.

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

而由于$C_n^k ( n - k ) ! = C_n^{ n - k } ( n - k ) ! = n^{ \underline{ n - k } } = \frac{ n ! }{ k ! } \\$.因此后半部分也得证.

$\left \{ \begin{array}{ c } n + m + 1 \ m\end{array} \right \} = \sum_{ k = 0 }^m k \left \{ \begin{array}{ c } n + k \ k\end{array} \right \} \\$.
$\left [ \begin{array}{ c } n + m + 1 \ m\end{array} \right ] \sum_{ k = 0 }^m ( n + k ) \left [ \begin{array}{ c } n + k \ k\end{array} \right ] \\$.

证明:

先考虑前者,我们将$n + k$个位置分到$k$个集合之后.还剩下$( n + m + 1 ) - ( n + k ) = ( m - k + 1 )$个数,剩下$( m - k )$个集合.

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

$C_n^m ( n - 1 )^{ \underline{ n - m } } = \sum_{ k = m }^n \left [ \begin{array}{ c } n \ k\end{array} \right ] \left \{ \begin{array}{ c } k \ m\end{array} \right \} \\$.

证明:

考虑$( n - 1 )^{ \underline{ n - m } } = \frac{ ( n - 1 ) ! }{ ( m - 1 ) ! } \\$,不妨设$f ( n , m ) = \sum_{ k = m }^n \left [ \begin{array}{ c } n \ k\end{array} \right ] \left \{ \begin{array}{ c } k \ m\end{array} \right \} \\$,相当于将$n$个数分成非空$m$组,然后组内的数要形成若干轮换的方案数.那么知道$f ( n , m ) = f ( n - 1 , m - 1 ) + ( n - 1 + m ) f ( n - 1 , m ) \\$.

设$g ( n , m ) = C_n^m \frac{ ( n - 1 ) ! }{ ( m - 1 ) ! } = \frac{ n ! ( n - 1 ) ! }{ m ! ( n - m ) ! ( m - 1 ) ! } \\$,那么知道:

$\begin{aligned} g ( n - 1 , m - 1 ) & = \frac{ ( n - 1 ) ! ( n - 2 ) ! }{ ( m - 1 ) ! ( n - m ) ! ( m - 2 ) ! } \\ g ( n - 1 , m ) & = \frac{ ( n - 1 ) ! ( n - 2 ) ! }{ m ! ( n - 1 - m ) ! ( m - 2 ) ! } \\ \end{aligned}$

显然$g ( n , m ) = g ( n - 1 , m - 1 ) + ( n - 1 + m ) g ( n - 1 , m ) \\$,数学归纳即可.

$C_n^m = \frac{ n ! }{ m ! ( n - m ) ! } = \sum_{ k = m }^n \left \{ \begin{array}{ c } n + 1 \ k + 1\end{array} \right \} \left [ \begin{array}{ c } k \ m\end{array} \right ] ( - 1 )^{ m - k } \\$.
$n^{ \underline{ n - m } } = \frac{ n ! }{ m ! } = \sum_{ k = m }^n \left [ \begin{array}{ c } n + 1 \ k + 1\end{array} \right ] \left \{ \begin{array}{ c } k \ m\end{array} \right \} ( - 1 )^{ m - k } ，其中 m \leq n \\$.

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

$\left \{ \begin{array}{ c } n \ l + m\end{array} \right \} C_{ l + m }^l = \sum_{ k = l }^n \left \{ \begin{array}{ c } k \ l\end{array} \right \} \left \{ \begin{array}{ c } n - k \ m\end{array} \right \} C_n^k \\$.
$\left [ \begin{array}{ c } n \ l + m\end{array} \right ] C_{ l + m }^l = \sum_{ k = l }^n \left [ \begin{array}{ c } k \ l\end{array} \right ] \left [ \begin{array}{ c } n - k \ m\end{array} \right ] C_n^k \\$.

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

欧拉数

记$\left \langle \begin{array}\ n \ k\end{array} \right \rangle$表示$\{ 1 , 2 , . . . , n \}$的排列$a$中满足这条性质的排列个数:存在且只存在$k$个升高,换句话说,存在且只存在$k$个$i$,满足$1 \leq i < n$,$a_i < a_{ i + 1 }$.不难发现$\left \langle \begin{array}\ n \ k\end{array} \right \rangle = \left \langle \begin{array}\ n \ n - k - 1\end{array} \right \rangle$.

考虑在一个$\{ 1 , 2 , . . . , n - 1 \}$的排列中插入$n$,设插入的位置是原本$a_i$的后面,那么要么原本$a_i < a_{ i + 1 }$,要么反之.前者不会改变排列的升高的数量,后者则会增加$1$.另外还有一种情况是插入到了序列最前面.于是我们自然得到:$\left \langle \begin{array}\ n \ k\end{array} \right \rangle = ( k + 1 ) \left \langle \begin{array}\ n - 1 \ k\end{array} \right \rangle + ( n - k ) \left \langle \begin{array}\ n - 1 \ k - 1\end{array} \right \rangle$.

特别地,我们令$\left \langle \begin{array}\ 0 \ k\end{array} \right \rangle = [ k = 0 ]$,若$k < 0$,则$\left \langle \begin{array}\ n \ k\end{array} \right \rangle = 0$.

欧拉数与二项式系数

我们有Worpitzky恒等式:

$x^n = \sum_{ k \geq 0 } \binom{ x + k }{ n } \left \langle \begin{array} \\ n \\ k \end{array} \right \rangle , n \in \mathbb{ N }$

还有另一个恒等式:

$\left \langle \begin{array} \\ n \\ m \end{array} \right \rangle = \sum_{ k = 0 }^m \binom{ n + 1 }{ k } ( m + 1 - k )^n ( - 1 )^k$

剩下的不会了.

伯努利数

定义$B_j$为第$j$个伯努利数,且满足$\sum_{ j = 0 }^m \binom{ m + 1 }{ j } B_j = [ m = 0 ] , m \geq 0 \\$.

定义$S_m ( n ) = \sum_{ i = 0 }^{ n - 1 } i^m$.

伯努利数满足公式:$S_m ( n ) = \cfrac{ 1 }{ m + 1 } \sum_{ k = 0 }^m \binom{ m + 1 }{ k } B_k n^{ m + 1 - k } \\$.

证明如下:

对$S_{ m + 1 } ( n )$使用扰动法,我们有:

$\begin{aligned} S_{ m + 1 } ( n ) + n^{ m + 1 } & = \sum_{ k = 0 }^{ n - 1 } ( k + 1 )^{ m + 1 } \\ & = \sum_{ k = 0 }^{ n - 1 } \sum_{ j = 0 }^{ m + 1 } \binom{ m + 1 }{ j } k^j \\ & = \sum_{ j = 0 }^{ m + 1 } \binom{ m + 1 }{ j } S_j ( n ) \\ & = \sum_{ j = 0 }^{ m } \binom{ m + 1 }{ j } S_j ( n ) + S_{ m + 1 } ( n ) \\ n^{ m + 1 } & = \sum_{ j = 0 }^m \binom{ m + 1 }{ j } S_j ( n ) \\ \end{aligned}$

接下来使用数学归纳,假设$0 \leq j < m$时该公式成立,并假设有$S_m ( n ) = \cfrac{ 1 }{ m + 1 } \sum_{ k = 0 }^m \binom{ m + 1 }{ k } B_k n^{ m + 1 - k } + \Delta \\$,我们只需要证明$\Delta = 0$.

$\begin{aligned} n^{ m + 1 } & = \sum_{ j = 0 }^m \binom{ m + 1 }{ j } \cfrac{ 1 }{ j + 1 } \sum_{ k = 0 }^j \binom{ j + 1 }{ k } B_k n^{ j + 1 - k } + ( m + 1 ) \Delta \\ & = \sum_{ 0 \leq k \leq j \leq m } \binom{ j + 1 }{ k } \binom{ m + 1 }{ j } \cfrac{ 1 }{ j + 1 } B_k n^{ j + 1 - k } + ( m + 1 ) \Delta \\ & = \sum_{ 0 \leq k \leq j \leq m } \binom{ j + 1 }{ j - k } \binom{ m + 1 }{ j } \cfrac{ 1 }{ j + 1 } B_{ j - k } n^{ k + 1 } + ( m + 1 ) \Delta \\ & = \sum_{ 0 \leq k \leq j \leq m } \binom{ j + 1 }{ k + 1 } \binom{ m + 1 }{ j } \cfrac{ 1 }{ j + 1 } B_{ j - k } n^{ k + 1 } + ( m + 1 ) \Delta \\ & = \sum_{ 0 \leq k \leq m } \cfrac{ n^{ k + 1 } }{ k + 1 } \sum_{ j = k }^m B_{ j - k } \binom{ m + 1 }{ j } \binom{ j }{ k } + ( m + 1 ) \Delta \\ & = \sum_{ 0 \leq k \leq m } \cfrac{ n^{ k + 1 } }{ k + 1 } \binom{ m + 1 }{ k } \sum_{ j = k }^m B_{ j - k } \binom{ m + 1 - k }{ j - k } + ( m + 1 ) \Delta \\ & = \sum_{ k = 0 }^m \cfrac{ n^{ k + 1 } }{ k + 1 } \binom{ m + 1 }{ k } \sum_{ j = 0 }^{ m - k } B_{ j } \binom{ m + 1 - k }{ j } + ( m + 1 ) \Delta \\ & = \sum_{ k = 0 }^m \cfrac{ n^{ k + 1 } }{ k + 1 } \binom{ m + 1 }{ k } [ m - k = 0 ] + ( m + 1 ) \Delta \\ & = n^{ m + 1 } + ( m + 1 ) \Delta \end{aligned}$

显然$\Delta = 0$,上式成立.

斐波那契数

定义斐波那契数$F_n = \begin{cases}0 & n = 0 \ 1 & n = 1 \ F_{ n - 1 } + F_{ n - 2 } & n > 1\end{cases}$.

斐波那契数的扩展定义

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

$F_{ n + 1 } F_{ n - 1 } - F_n^2 = ( - 1 )^n , n > 0$

事实上,如果我们将斐波那契数的递推式改写作:$F_n = F_{ n + 2 } - F_{ n + 1 }$,我们可以在$n \in \mathbb{ Z }$的时候定义斐波那契数,同样也是满足上面的恒等式的,而且我们可以发现:

$F_{ - n } = ( - 1 )^{ n - 1 } F_n , n \in \mathbb{ Z }$

斐波那契数与数论

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

$\begin{aligned} F_{ n + k } & = F_k F_{ n + 1 } + F_{ k - 1 } F_n \\ F_{ n + m + 1 } & = F_{ n + 1 } F_{ m + 1 } + F_n F_m \end{aligned}$

另外,如果我们在上面这个式子中取$k = wn , w \in \mathbb{ N }$并使用归纳法,我们又可以得到一个性质:$F_{ kn }$是$F_n$的倍数,$k \in \mathbb{ Z }$.

再观察这个式子,使用归纳法可以证明$\gcd ( F_{ n } , F_{ n - 1 } ) = 1$,进一步有:$\gcd ( F_{ n + m } , F_m ) = \gcd ( F_n , F_m )$.

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

$\gcd ( F_m , F_n ) = F_{ \gcd ( n , m ) }$

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

$F_n^2 | F_m \Leftrightarrow nF_n | m , n > 2$

这个引理的证明如下:

由于$F_{ n + 1 } \equiv F_{ n - 1 } \pmod{ F_n }$.于是我们有:$F_{ 2 n } = F_n F_{ n + 1 } + F_{ n - 1 } F_n$,也就是$F_{ 2 n } \equiv 2 F_n F_{ n + 1 } \pmod{ F_n^2 }$.

另外我们有:$F_{ 2 n + 1 } \equiv F_{ n + 1 }^2 \pmod{ F_n^2 }$.

同理,使用归纳法可以证明:$F_{ kn } \equiv kF_n F_{ n + 1 }^{ k - 1 } \pmod{ F_n^2 } , F_{ kn + 1 } \equiv F_{ n + 1 }^k \pmod{ F_n^2 }$.

而$F_{ n + 1 } \bot F_n$,于是$F_{ kn } \equiv 0 \pmod{ F_n^2 } \Leftrightarrow k \equiv 0 \pmod{ F_n } , n > 2$.

斐波那契数系

我们如果定义$j \gg k \Leftrightarrow j \geq k + 2$,那么有齐肯多夫定理:

每个正整数都有唯一的表示方式满足:$n = \sum_{ i = 1 }^r F_{ k_i } , \forall 1 \leq i < r , k_i \gg k_{ i + 1 } \gg 0$.

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

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

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

斐波那契数的封闭形式

使用生成函数,令$F ( z ) = \sum_{ k \geq 0 } F_k z^k$.那么不难发现$F ( z ) - zF ( z ) - z^2 F ( z ) = z$,也就是$F ( z ) = \cfrac{ z }{ 1 - z - z^2 }$.

考虑这个形式一定可以分解为$F ( z ) = \cfrac{ a }{ 1 - \alpha z } + \cfrac{ b }{ 1 - \beta z }$的形式,而这两种形式对应的生成函数都很显然.

进行因式分解,如果令$\phi = \cfrac{ 1 + \sqrt{ 5 } }{ 2 } , \hat \phi = \cfrac{ 1 - \sqrt{ 5 } }{ 2 }$,那么可以得到$F_n = \cfrac{ 1 }{ \sqrt{ 5 } } ( \phi^n - \hat \phi^n )$.

另外,由于$\hat \phi^n$的影响很小,于是又有$F_n = \lfloor \cfrac{ \phi^n }{ \sqrt{ 5 } } + 0 . 5 \rfloor$.

连项式

连项式多项式$K_n ( x_1 , x_2 , . . . , x_n )$定义为:$K_n ( x_1 , x_2 , . . . , x_n ) = \begin{cases}1 & n = 0 \ x_1 & n = 1 \ x_n K_{ n - 1 } ( x_1 , x_2 , . . . x_{ n - 1 } ) + K_{ n - 2 } ( x_1 , x_2 , . . . , x_{ n - 2 } ) & n \geq 2\end{cases}$.

通过定义不难发现:$K_n ( 1 , 1 , . . . , 1 ) = F_{ n + 1 }$.

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

于是我们有:

$\begin{aligned} K_n ( z , z , . . . , z ) & = \sum_{ k = 0 }^n \binom{ n - k }{ k } z^{ n - 2 k } \\ \end{aligned}$

另外,这也导出:$F_{ n + 1 } = \sum_{ k = 0 }^n \binom{ n - k }{ k } \\$.

考虑上面的构造过程,不难发现$K_n ( x_1 , x_2 , . . . , x_n ) = K_n ( x_n , x_{ n - 1 } , . . . , x_1 )$.

于是递归式可以写成:$K_n ( x_1 , x_2 , . . . , x_n ) = x_1 K_{ n - 1 } ( x_2 , x_3 , . . . x_{ n } ) + K_{ n - 2 } ( x_3 , x_4 , . . . , x_{ n } )$.

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

$\begin{aligned} K_{ m + n } ( x_1 , . . . , x_m , x_{ m + 1 } , . . . , x_{ n + m } ) & = \\ K_m ( x_1 , . . . , x_m ) K_n ( x_{ m + 1 } , . . . , x_{ n + m } ) + K_{ m - 1 } ( x_1 , . . . , x_{ m - 1 } ) K_{ n - 1 } ( x_{ m + 2 } , . . . , x_{ n + m } ) \end{aligned}$

另外,根据连项式的定义,不难导出$K_n ( x_1 , . . . , x_n + y ) = K_n ( x_1 , . . . , x_n ) + K_{ n - 1 } ( x_1 , . . . , x_{ n - 1 } ) y$.

由这个公式可以推出:$\cfrac{ K_{ n + 1 } ( a_0 , . . . , a_n ) }{ K_n ( a_1 , . . . , a_n ) } = \cfrac{ K_n ( a_0 , . . . , a_{ n - 1 } + \cfrac{ 1 }{ a_n } ) }{ K_{ n - 1 } ( a_1 , . . . , a_{ n - 1 } + \cfrac{ 1 }{ a_n } ) }$.

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

$\cfrac{ K_{ n + 1 } ( a_0 , . . . , a_n ) }{ K_n ( a_1 , . . . , a_n ) } = a_0 + \cfrac{ 1 }{ a_1 + \cfrac{ 1 }{ a_2 + \cfrac{ 1 }{ a_3 + . . . } } }$

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