组合数学

发表于 更新于 分类于 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{(2r)^{\underline{2k}}}{2^{2k}},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}\and r<k\)时,该公式给出\(0\).

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

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

基本的二项式恒等式

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

证明根据定义是显然的.

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

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

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

证明根据定义是显然的.

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

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

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

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

不过事实上,直接用吸收恒等式就可以证明: \[ 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} \]

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

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

  1. \(\binom{r}{m}\binom{m}{k}=\binom{r}{k}\binom{r-k}{m-k},n,k\in\mathbb{Z}\\\).

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

  1. 平行求和法:\(\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\)个数.

  1. 上指标求和法:\(\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}\\\),这也就是有限微积分的公式中的一个.

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

可以使用组合意义证明.

二项式定理有一些有用的特殊情况: \[ \sum_{0\leq k\leq n}\binom{n}{k}=2^n,n\in\mathbb{N}\\ \] 在二项式定理中令\(x=y=1\)即可证明. \[ \sum_{0\leq k\leq n}(-1)^k\binom{n}{k}=0^n=[n=0],n\in\mathbb{N}\\ \] 在二项式定理中令\(x=-1,y=1\)即可证明,值得一提的是,当\(n=0\)的时候这个式子给出\(1\),并在其他情况下给出\(0\),这个式子是二项式反演的基础.

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

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

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

证明与二项式定理类似.

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

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

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

  1. 范德蒙德卷积的变式:\(\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}\),然后运用范德蒙德卷积即可得到答案.

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

根据定义显然.

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

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

证明如下: \[ \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} \]

  1. \(\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\\\).

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

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

可以数学归纳证明.

  1. \(\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}}\\\).

有: \[ \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} \]

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

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

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

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

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

不妨令左边的值为\(S_m\),我们有: \[ S_m=\sum_{k\leq m}\binom{m+r}{k}x^ky^{m-k}=\sum_{k\leq m}\binom{m+r-1}{k}x^ky^{m-k}+\sum_{k\leq m}\binom{m+r-1}{k-1}x^ky^{m-k}\\ =y\sum_{k<m}\binom{m-1+r}{k}x^ky^{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 \] 左右两边满足相同递归式,通过数学归纳法不难证明二者相等.

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

考虑\((7)\),将\(x=y=1,r=m+1\)带入,得到: \[ \sum_{k\leq m}\binom{2m+1}{k}=\sum_{k\leq m}\binom{m+k}{k}2^{m-k}\\ 2^{2m}=\sum_{k\leq m}\binom{m+k}{k}2^{m-k}\\ 2^m=\sum_{k\leq m}\binom{m+k}{k}2^{-k} \]

  1. \(\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}\\\).

可以数学归纳证明.

  1. \(\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}\\\).

可以数学归纳证明.

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

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

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

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

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

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

即\((2)\)的变形.

  1. \(\sum_{k}\binom{n}{2k}\binom{2k}{k}2^{-2k}=\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}\)必有一个是自然数,因此可以直接用范德蒙德卷积的变形.

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

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

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

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

  1. \(\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}}\),直接做高阶差分即可得到这个式子.

  1. \(\sum_{k=0}^n\binom{r}{k}\binom{r}{n-k}(-1)^k=[n\ is\ 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\)表示:长度为\(2n\)的合法括号序列个数.

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

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

递归定义:\(f_n=\sum_{i=0}^{n-1}f_if_{n-1-i}\).

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

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

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

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

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

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

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

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

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

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

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

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

使用一下上一步的通项公式:\(\begin{cases} f_n=\frac{(2n)!}{n!(n+1)!}\\ f_{n-1}=\frac{(2n-2)!}{(n-1)!(n)!} \end{cases}\\\) 不难发现\(f_n=\frac{(2n-1)(2n)}{n(n+1)}f_{n-1}\\\).整理,得到\(f_n=\frac{4n-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{2n+k-1}{n} \] 我们可以这么理解它:它指的是一个长度为\(n+k-1\)的括号序列,前\(k-1\)个必须是左括号的方案数.为啥呢?因为这样这个括号序列必须写成\((((A)B)C)D\)之类的形式,等价于卷积.

那么证明就很简单了,类似反射容斥,有: \[ C^{(k)}_n=\binom{2n+k-1}{n}-\binom{2n+k-1}{n-1}\\ =\frac{k}{n+k}\binom{2n+k-1}{n} \]

Example([HNOI2009]有趣的数列)

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

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

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

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

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

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

  1. \(x\)节点的祖先数量不超过\(y-1\)个(深度小于等于\(y\)).
  2. \(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}\).

记: \[ 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}\\ \] 注意到这等价于卡特兰数的\(k\)次卷积,有: \[ L_p=C_{x-p-1}^{(p+1)}\\ R_q=C^{(q+1)}_{n-x-q}\\ \] 此时的答案自然是\(f_{p+q+1}=L_pR_q\binom{p+q}{q}\),做卷积.

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

二项式系数的处理

通过恒等式变形求解

Example1

求\(\sum_{k=0}^nk\binom{m-k-1}{m-n-1},n,m\in\mathbb{N}\and m>n\\\).

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

于是: \[ \sum_{k=0}^nk\binom{m-k-1}{m-n-1}=\sum_{k=0}^nm\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} \] 不妨令\(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}\)带入: \[ \sum_{k=0}^nk\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} \]

Example2

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

第一反应仍然是使用吸收恒等式,但是注意到\(n\)和\(s\)的范围不一样,由于吸收恒等式的范围很松,因此应选择一个范围更松的数吸收,这样才能保证另一个数范围的特殊性,于是有: \[ \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} \]

Example3

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

我们有: \[ \sum_{0\leq k}\binom{n+k}{2k}\binom{2k}{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] \]

Example4

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

考虑恒等式扩展的二项式恒等式(整数范围内)的\((1)\),我们有: \[ \sum_{k\geq 0}\binom{n+k}{m+2k}\binom{2k}{k}\cfrac{(-1)^k}{k+1}=\sum_{k\geq 0}\sum_{0\leq j\leq n+k-1}\binom{n+k-1-j}{2k}\binom{j}{m-1}\binom{2k}{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}{2k}\binom{2k}{k}\cfrac{(-1)^k}{k+1} \] 注意到如果\(j+1-n\geq 0\),则\(\binom{n+k-1-j}{2k}\\\)应为\(0\).所以有: \[ \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}{2k}\binom{2k}{k}\cfrac{(-1)^k}{k+1}\\ =\sum_{0\leq j<n}\binom{j}{m-1}[n-1-j=0]=\binom{n-1}{m-1} \]

Example5

求\(\sum_{k=0}^n(C_n^k)^2\). \[ \sum_{k=0}^n(C_n^k)^2=\sum_{k=0}^nC_{n}^k\times C_{n}^{n-k}=C_n^{2n} \]

转化为递归式/和式求解

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}\).

而我们有: \[ 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} \] 也即\(R_n\)具有周期性,不难计算前几项答案,最后有\(Q_n\begin{cases}1&n=0\\0&n\ is \ odd\\-1&n>0\and n\ is\ 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}\\\),则有: \[ 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}^kC_k^jf(n-1,r-j)\\ \] 整理上式,得到:\(f(n,r)=\sum_{j=0}^kC_k^jf(n-1,r-j)\\\).

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

利用微积分求解

Example

求\(\sum_{k=1}^nk^2C_n^k\). \[ ((1+x)^n)=(\sum_{k=0}^nC_n^kx^{k})\\ ((1+x)^n)'=(\sum_{k=0}^nC_n^kx^{k})'\\ n(1+x)^{n-1}=\sum_{k=0}^nkC_n^kx^{k-1}\\ nx(1+x)^{n-1}=\sum_{k=0}^nkC_n^kx^{k}\\ (nx(1+x)^{n-1})'=(\sum_{k=0}^nkC_n^kx^{k})'\\ n((1+x)^{n-1}+(n-1)x(1+x)^{n-2})=\sum_{k=0}^nk^2C_n^kx^{k-1}\\ \] 取\(x=1\),则原式\(=n(n+1)2^{n-2}\).

转化为二维平面

Example1

多次询问给定\(k,r\),\(\sum k\leq 2n,r< 2n-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 2n\).我们需要另辟蹊径.

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

直接拆组合数,我们有: \[ 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}\\ =2f_{r-1}-\binom{r-1}{n} \]

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 iC_{p-1}^{i-1}\equiv 0(\mod p)\\\).

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

令\(n=k_1p+b_1\),\(m=k_2p+b_2\),则\((1+x)^n=(1+x)^{k_1p}(1+x)^{b_1}\\\).

而\((1+x)^{k_1p}\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^mx^m\equiv C_{k_1}^{k_2}x^{k_2p}C_{b1}^{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\).

所以原式化简为: \[ \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\\ \] 然后呢?不难发现后面那一串是范德蒙德卷积的形式,就可以写成: \[ \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)] \]

扩展Lucas定理

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

那现在问题转化为要求\(C_n^m\mod p^k\),其中\(p\in 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\\\).

注意到: \[ 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) \] 递归求解即可.

ps:

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

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

斯特林数

第一类斯特林数

$ nk\\(:长度为\)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}\\\).

基本斯特林恒等式

  1. \(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}}\\\),我们要证\(x^{n}=\sum_{k=0}^{n}\left\{ \begin{array}{c}n\\k\end{array} \right\}x^{\underline{k}} \\\).也就是证明: \[ 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}}\\ \] 考虑\((x-k)x^{\underline{k}}=x^{\underline{k+1}}\),所以\(x\cdot x^{\underline{k}}=x^{\underline{k+1}}+kx^{\underline{k}}\\\).那么左边即: \[ \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}}\\ \\ \] 至于后半段,由于\(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\),我们有: \[ (-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}} \]

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

  2. \(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)前半段的推导即可得到,后者同样可以使用下降幂和上升幂的转化来得到.

  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\).前半部分是同理的.这个公式是斯特林反演的基础.

  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\}\\\).

  2. \(\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\)组,再把剩下的分到一组.对于后者,也可以同样考虑组合意义.

补充斯特林恒等式

  1. \(\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}\\\).

  2. \(\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),根据二项式反演可知.

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

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

  1. \(\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\)不同的时候最小值是不同的,因此一定不重不漏.

  1. \(\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!}\\\).因此后半部分也得证.

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

  2. \(\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\))单独自己集合的后缀.所以这个递推成立.后者也可以同样证明.

  1. \(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)!}\\\),那么知道: \[ 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)!}\\ \] 显然\(g(n,m)=g(n-1,m-1)+(n-1+m)g(n-1,m)\\\),数学归纳即可.

  1. \(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}\\\).

  2. \(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),对其做一遍斯特林反演即可.

  1. \(\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\\\).

  2. \(\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_kn^{m+1-k}\\\).

证明如下:

对\(S_{m+1}(n)\)使用扰动法,我们有: \[ 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)\\ \] 接下来使用数学归纳,假设\(0\leq j<m\)时该公式成立,并假设有\(S_m(n)=\cfrac{1}{m+1}\sum_{k=0}^m\binom{m+1}{k}B_kn^{m+1-k}+\Delta\\\),我们只需要证明\(\Delta=0\). \[ n^{m+1}=\sum_{j=0}^m\binom{m+1}{j}\cfrac{1}{j+1}\sum_{k=0}^j\binom{j+1}{k}B_kn^{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_kn^{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}^mB_{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}^mB_{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 \] 显然\(\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} \]

斐波那契数与数论

如果我们考虑不断使用斐波那契递推式展开,不难发现: \[ F_{n+k}=F_kF_{n+1}+F_{k-1}F_n\\ F_{n+m+1}=F_{n+1}F_{m+1}+F_nF_m \] 另外,如果我们在上面这个式子中取\(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_{2n}=F_nF_{n+1}+F_{n-1}F_n\),也就是\(F_{2n}\equiv 2F_nF_{n+1}\pmod {F_n^2}\).

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

同理,使用归纳法可以证明:\(F_{kn}\equiv kF_nF_{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}^rF_{k_i},\forall 1\leq i< r,k_i\gg k_{i+1}\gg 0\).

首先证明存在性:我们考虑数学归纳,对于一个数n,如果\(\exist k\)满足\(F_k=n\),则显然成立,不然,应\(\exist 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_kz^k\).那么不难发现\(F(z)-zF(z)-z^2F(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_nK_{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-2k\)个’.’,则有\(\binom{n-k}{k}\)种不同的排列方式.

于是我们有: \[ K_n(z,z,...,z)=\sum_{k=0}^n\binom{n-k}{k}z^{n-2k}\\ \] 另外,这也导出:\(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_1K_{n-1}(x_2,x_3,...x_{n})+K_{n-2}(x_3,x_4,...,x_{n})\).

进一步地,不断展开后得到: \[ 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}) \] 另外,根据连项式的定义,不难导出\(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树有很大关系,暂略.