OI中组合数学公式和定理90%歼灭

组合数学

基础概念

加法和乘法原理

加法原理

同一步下的不同选择，可以通过累加得到方案数。

乘法原理

整个流程的方案数可以由每一步的方案数相乘得到。

有了加法原理和乘法原理，就可以解决一些没有选择导致分支的问题了。

例题1

有 nn 个篮子，第 i 篮子有 ai 有水果，每个水果各不相同，问每个篮子选出一个得到的水果的方案数。

解答：

用加法和乘法原理，那么每个篮子选出的方案数为 ai ，总共就是 ∏ai 种方案。

排列和组合

排列数

从 n 个不同元素中选出 m 个，按照一定顺序排列，简而言之就是选出一个数列的方案数。

Amn=n(n−1)(n−2)..(n−m+1)=n!(n−m)!

组合数

从 n 个不同元素中选出 m 个的方案数，换句话就是选出一个集合的方案数。

Cmn=Amnm!=n!m!(n−m)!

其实排列数可以看做在选出 m 个数后还有对这 m 个数做一个全排列，所以多一个 m!

因为组合数我们用得多一点，所以我们一般用二项式系数来表示组合数，也就是说：

Cmn=(nm)

然后定义一些离谱的情况： m>n 或者 m<0 时， (nm)=0

多重组合数

多重组合数和多重集排列数

多重集合，也叫可重集。一个多重集合 S={a1⋅n1,a1⋅n2,...,am⋅nm} （ni 表示元素个数， ai 表示元素）的排列数（也被称为多重组合数）：

(nn1,n2,...,nm)=n!n1!n2!...nm!

相当于是所有数的全排列数再除去相同元素的全排列数。

顺便补充一嘴：

(nm)=(nn,n−m)

多重集组合数

一个多重集合 S={a1⋅n1,a1⋅n2,...,ak⋅nk} 的组合数，就是从中选出 r 个，得到不同可重集的方案数。

这个怎么弄？先来个简单的的，我们使 r<ni。

这个我们考虑用插板法来求。可以看做我们现在有 r 个小球，然后现在往里面插板来分组。

最初的时候，我们有 r 个球，那么我们有 r+1 个位置是可以插空的。当我们插入了一个板子之后，我们可以插入的位置就又多了一个，后面就同理了。

于是乘法原理加上除去板子的全排列可以得到答案：

(r+k−1)!r!(k−1)!=(k+r−1k−1)=(k+r−1r)

现在考虑把 r<ni 的限制拿掉，怎么做？

这个要容斥原理！但是在这篇博客里我们还没有学！超纲了，我们等会讲容斥的时候再说。

CF451E

不相邻排列

1→n 个自然数中选出 k 个，使得他们互不相邻的方案数？

答案是 (n−k+1k) ，相当于是留了 k−1 个空加在每两个被选择的位置中间。

组合恒等式

1.对称式

(nm)=(nn−m)

证明：

从组合意义上来说容易证明。因为你 n 中拿 m 个等价于有 n−m 个不拿。

2.二项式定理

(x+y)n=n∑i=0(ni)xiyn−i

证明：

从组合意义来证明。

我们把 (x+y)n 看作是有 n 个 (x+y) 相乘，那么得到一个 xayn−a 相当于是从 n 个 (x+y) 中选出 a 个 (x+y) 中的 x 相乘，那么结果的多项式中就有一项是 (na)xayn−a 。所以的这种项都满足这种情况，那么公式可得。

Q.E.D.

其实不一定要求必须是两元的，多元的也是同理。

然后我们可以得到多项式定理：

(x1+x2+...+xm)n=∑n1+n2+...+nm=n(nn1,n2,...,nm)xn11xn22...xnmm

证明：

同二项式定理证明，对于 xn11xn22...xnmm 这一项的系数为 (nn1)(n−n1n2)...(n−n1−n2−...−nm−1nm) 。

展开发现可以抵消一些东西，于是上面的系数就等于：

n!n1!n2!...nm!=(nn1,n2,...,nm)

Q.E.D.

3.递推式1

(nk)=(n−1k−1)+(n−1k)

帕斯卡定理，你也可以说是杨辉三角。我们知道 (x+y)n 得到的多项式是系数满足杨辉三角的，我们知道了二项式定理的话，发现这个东西实际上是组合数，所以实际上是组合数的同层展开是满足杨辉三角的。但是证明的话显然不能这么证明。

证明：

我们一个数一个数看这个数是否选取，假设现在已经看了 n−1 个数，选了 x 个数。我们考虑如果得到 (nk)

那么接下来这个数选或不选分别造成 1 和 0 的贡献，也就是说：

如果接下来这个数选，那么只有 x=k−1 的情况符合条件。否则只有 x=k 的情况符合条件。于是加法原理把两种情况的方案数加起来即可。

Q.E.D.

4.特殊的二项式定理

(n0)+(n1)+...+(nn)=2n

实际上是 (1+1)n ，当然也可以从组合意义上证明。

n∑i=0(−1)i(ni)=[n=0]

实际上是 (1−1)n ，我称之为第一类二项式反演。

5.递推式2

(nk)=nk(n−1k−1)

按定义来就没了，简单提一下。

6.积式

(nr)(rk)=(nk)(n−kr−k)

定义展开左边上下分子分母同乘 (n−k)! 即可证明。

7.变下项求和式

n∑k=0k(nk)=n2n−1

证明：

n∑k=0k(nk)=n∑k=1k(nk)=n∑k=1n(n−1k−1)=nn−1∑i=0(n−1i)=n2n−1

Q.E.D.

n∑k=0k2(nk)=n(n−1)2n−2

证明和上面差不多，就不证了。其实你想拆可以一直这么拆。

8.变上项求和式

n∑l=0(lk)=(n+1k+1)

证明：

采用组合分析。

指定 n+1 个数的集合 S={a1,a2,...,an+1}

先考虑右边的组合意义，即从 n+1 个数中选出 k+1 个。

左边的组合意义：相当于是总共 n+1 种不累加的情况的加法原理。

第一种：在指定必须选择 a1 ，然后从剩余的 n 个数中选择 k 个，方案数 (nk)

第二种：在指定必须不选择 a1 而选择 a2 ，然后从剩余的 n−1 个数中选择 k 个，方案数 (n−1k)

第三种：在指定必须不选择 a1,a2 而选择 a3 ，然后从剩余的 n−2 个数中选择 k 个，方案数 (n−2k)

⋮

第 n+1 种：在指定必须不选择 a1,a2,...,an 而选择 an+1 ，然后从剩余的 0 个数中选择 k 个，方案数 (0k)

总体的组合意义 ∑ni=0(ik) 等价于从 n+1 个数中选出 k+1 个，那么等式左右两边组合意义相同，等式成立。

Q.E.D.

9.积和式

r∑k=0(mk)(nr−k)=(m+nr),r≤min{n,m}

证明：

指定集合 A={a1,a2,...,am} 和 B={b1,b2,...,bn}。

右边问题等价于从 A,B 两个集合中选出 r 个的方案数。

左边问题等价于：

对于 k∈[0,r]，先在 A 中先取出 k 个，然后在 B 中选出 r−k 个的总方案数。

即 A,B 中总共选出 r 个的方案数。

所以左右两个问题组合意义等价，等式成立。

Q.E.D.

10.第二类二项式反演

f(n)=n∑i=0(−1)i(ni)g(i)⇔g(n)=n∑i=0(−1)i(ni)f(i)

证明：

已知：g(n)=∑ni=0(−1)i(ni)f(i)

则：

n∑i=0(−1)i(ni)g(i)=n∑i=0(−1)i(ni)i∑j=0(−1)j(ij)f(j)=n∑i=0i∑j=0(−1)i+j(ni)(ij)f(j)=n∑i=0i∑j=0(−1)i+j(nj)(n−ji−j)f(j)=n∑j=0(−1)j(nj)f(j)n∑i=j(−1)i(n−ji−j)=n∑j=0(−1)j(nj)f(j)n−j∑i=0(−1)i+j(n−ji)=n∑j=0(nj)f(j)n−j∑i=0(−1)i(−1)2j(n−ji)=n∑j=0(nj)f(j)n−j∑i=0(−1)i(n−ji)=n∑j=0(nj)f(j)[n−j=0]=f(n)

Q.E.D.

然后我们还可以得到一个扩展：

f(n)=n∑i=0(ni)g(i)⇔g(n)=n∑i=0(−1)n−i(ni)f(i)

证明：

令 G(n)=(−1)ng(n) ，有：

若 f(n)=∑ni=0(−1)i(ni)G(i) 成立，有 G(n)=∑ni=0(−1)i(ni)f(i)

即

G(n)=n∑i=0(−1)i(ni)f(i)∴g(n)(−1)n=n∑i=0(−1)i(ni)f(i)

当 n 为偶数，则 n−i 与 i 奇偶性相同，有 g(n)=∑ni=0(−1)n−i(ni)f(i)

当 n 为奇数，则 n−i 与 i 奇偶性相反，同样有 g(n)=∑ni=0(−1)n−i(ni)f(i)

由此有 g(n)=∑ni=0(−1)n−i(ni)f(i)

Q.E.D.

圆排列

考虑 n 个人围成圆的圆排列方案数为 Qnn 。我们发现对于一个圆，从每个地方断开都可以形成一个新的排列，所以：

Qnn×n=Ann⇒Qnn=Qnnn=(n−1)!

所以 Qmn=Amnm=n!r(n−r)!

错位排序

设 f(n) 表示将 n 个编号为 1,2,...,n 的物品，放到编号为 1,2,...,n 的位置中，使每个物品放置的位置的编号与物品的编号都相同的方案数。

我们考虑递推，考虑目前放置第 n 个物品，先暂时放在第 n 个位置，而保证其他 n−1 个物品都放在 [1,n−1] 的位置。然后考虑前面的一个物品和第 n 号物品交换位置，可知 f(n) 只能由两种情况递推而来。

第一种情况：前面的 n−1 个物品全部错位。这个直接就是每个物品都可以换。总共 n−1 种交换方法。

第二种情况：前面 n−1 个中除一个物品外全部错位。n 必然与这个不错位的物品换位，这个不错位物品有 n−1 种可能。

那么可得递推式：

f(n)=(n−1)(f(n−1)+f(n−2))

鸽巢原理

假设有 n+1 个物品，那么将物品分为 n 组后，至少有一组含有两个及以上的物品。

证明：

假设每个分组都只有至多 1 个物品，那么最多有 n 个物品，与有 n+1 个物品的事实矛盾。

由此得证。Q.E.D.

一个扩展：

将 n 个物品分为 k 组，至少存在一个分组含有大于等于 ⌈nk⌉ 个物品。

同样可以反证，简单就不证了。

容斥原理

有一个集合的集合 A={Si} ，那么：

|n⋃i=1Si|=n∑i=1(−1)i−1∑{ak},ak<ak+1|i⋂j=1Saj|

证明：

如果对于每个元素都保证其出现一次，那么上式正确。

现在考虑对于一个元素 x ，证明其出现次数为 1 。假设它在集合 T1,T2,...,Tk 中出现。

那么其出现次数为：

cnt=|{Ti}|−|{Ti∩Tj|i<j}|+...+(−1)k−1|{k⋂i=1Tai|{ai},ai<ai+1}|=(k1)−(k2)+...+(−1)k−1(kk)=(k0)−k∑i=0(−1)i(ki)=1−(1−1)k=1

可知出现次数为 1 。Q.E.D.

容斥原理的补集形式

|n⋂i=1Si|=|U|−|n⋃i=1¯Si|

右边容斥计算即可。

容斥原理一般化

对于两个关于集合的函数 f(S),g(S) ，如果：

f(S)=∑T⊆Sg(T)

那么有：

g(S)=∑T⊆S(−1)|S|−|T|f(T)

证明：

∑T⊆S(−1)|S|−|T|f(T)=∑T⊆S(−1)|S|−|T|∑Q⊆Tg(Q)=∑Qg(Q)∑Q⊆T⊆S(−1)|S|−|T|=∑Qg(Q)∑T⊆(S/Q)(−1)|S/Q|−|T|

我们知道，对于一个关于集合的函数 F(P)=∑T⊆(P)(−1)|P|−|T|，有：

F(P)=∑T⊆P(−1)|P|−|T|=|P|∑i=0(|P|i)(−1)|P|−i=(1−1)|P|=0|P|

那么我们就有：

∑T⊆S(−1)|S|−|T|f(T)=∑Qg(Q)0|S/Q|=g(S)

Q.E.D.

还有一个倒过来的推论（补集形式）

如果：

f(S)=∑S⊆Tg(T)

那么有：

g(S)=∑S⊆T(−1)|S|−|T|f(T)

Min_max 容斥

对于 n 长全序序列 {xi} ，S={1,2,...,n}，有：

maxi∈Skxi=∑T⊆S(−1)|T|−k(|T|−1k−1)minj⊆Txjmini∈Skxi=∑T⊆S(−1)|T|−k(|T|−1k−1)maxj⊆Txj

证明：

由于全序的对称性，我们可以知道 min 和 max 互换的话，效果也是一样的，所以我们只考虑证明第一个式子。

考虑构造一个系数 ai，满足：

maxi∈Skxi=∑∅≠T⊆Sa|T| mini∈Txi

那么：

maxi∈Skxi=∑∅≠T⊆Sa|T| mini∈Txi=n∑i=1maxj∈Sii∑j=1aj(i−1j−1)

解释一下，这里是对于每个元素统计其贡献，对于第 i 大的数，我们可以知道其在所处集合作为最小值的集合的大小小于等于 i 。然后我们可以枚举集合的大小，显然比这个数大的有 i−1 个，我们从中再选出 j−1 个和当前这个数组成集合，那么上式可得。

然后我们知道，当 ∑ij=1aj(i−1j−1)=[i=k] 时，则构造成立。

令 g(n)=[n+1=k],f(n)=an+1 那么：

i∑j=1aj(i−1j−1)=[i=k]∴i−1∑j=0f(j)(i−1j)=g(i−1)

由二项式反演：

f(i−1)=i−1∑j=0(−1)i−1−j(i−1j)g(j)∴ai=i−1∑j=0(−1)i−1−j(i−1j)g(j)=i∑j=1(−1)i−j(i−1j−1)g(j−1)=i∑j=1(−1)i−j(i−1j−1)[j=k]=(−1)i−k(i−1k−1)

因此：

maxi∈Skxi=∑∅≠T⊆Sa|T| mini∈Txi=∑∅≠T⊆S(−1)|T|−k(|T|−1k−1)mini∈Txi=∑T⊆S(−1)|T|−k(|T|−1k−1)mini∈Txi

Q.E.D.

其实 min_max 容斥 在期望意义下也满足：

E(maxi∈Skxi)=∑T⊆S(−1)|T|−k(|T|−1k−1)E(minj⊆Txj)E(mini∈Skxi)=∑T⊆S(−1)|T|−k(|T|−1k−1)E(maxj⊆Txj)

由期望线性性可知。

再论多重集组合数

我们前面提到过这个问题是需要容斥原理的。现在我们已经可以解决这个问题了。

回顾一下问题：一个多重集合 S={a1⋅n1,a1⋅n2,...,ak⋅nk} 的组合数，就是从中选出 r 个，得到不同可重集的方案数。每个数被选出 xi 个。

设一个集合 Si 表示不满足 xi≤ni ，即满足 xi≥ni+1 的集合。

那么答案为：

|U|−|k⋃i=1Si|

后面那半部分我们容斥计算：

|k⋃i=1Si|=∑i|Si|−∑i,j|Si∩Sj|+...+(−1)k−1|k⋂i=1Si|=∑i(k+r−ni−2k−1)−(k+r−ni−nj−3k−1)+...+(−1)k−1(k+r−∑ki=1ni−k−1k−1)

意义就是提前为其留出一些空间使其满足条件。

那么：

|U|−|k⋃i=1Si|=k∑i=0(−1)i∑|{ak}|=i,ak<ak+1(k+r−1−∑ij=1nai−ik−1)

那么就可以切掉这个题了

CF451E

但是这个题还有一个小技巧。

发现范围巨大，不好直接算组合数，但是 n 很小，我们把组合的求和转换为与 n 相关的算法。具体转换类似下方的做法。

(k+r−1k−1)=(k+r−1)!(k−1)!(r)!=(k+r−1∏i=r+1i)×(k−1∏i=1inv[i])

卡特兰数（Catalan）

卡特兰数 Catn ，是下问题的答案：从 (0,0) 出发，可以按照向量 (1,0) 和 (0,1) 游走，不越过（可以碰到）第一象限角平分线的情况下，到达 (n,n) 的方案数。（就是只能在这条线下方走）

我们通过解决这个问题可得到卡特兰数的公式。

不越过第一象限角平分线 y=x ，等价于不触碰 y=x+1 。

然后你发现如果你碰到了直线 y=x+1 ，那么可以发现从这个触碰点到 (n,n) 的方案数和到 (n−1,n+1) （(n,n) 关于 y=x+1 的对称点）的方案数相同，因为在两边走是对称的。然后我们知道到达 (n−1,n+1) 必然经过 y=x+1 ，所以只需要到达 (n,n) 的方案数减去到达 (n−1,n+1) 的方案数即可。

即 Catn=(2nn)−(2nn−1)

通项公式

Catn=(2nn)−(2nn−1)=(2n)!n!n!−(2n)!(n+1)!(n−1)!=1n+1(2n)!(n+1)−(2n)!nn!n!=1n+1(2n)!n!n!=1n+1(2nn)

递推公式

Catn+1=1n+2(2n+2n+1)=1n+21n+1(2n+1)(2n+2)n+1(2n)!n!n=4n+2n+21n+1(2nn)=4n+2n+2Catn

然后初始状态 Cat0=Cat1=1

递归公式

Catn={1n≤1∑ni=1Cati−1Catn−i

证明：

对于 2n 长的括号序列，如果最后一个右括号与第 i 个左括号匹配，那么前 (i−1) 个左括号的匹配肯定构成一个合法括号序列。这个 i 满足 1≤i≤n 。那么公式可得。

Q.E.D.

应用

我们发现其实对于所有的可以转化为如下问题的问题，都可以考虑卡特兰数列：

长度为 2n 的合法括号序列计数。

这个问题可以抽象上坐标轴，即从 (0,0) 通过向量 (1,1) 和 (−1,−1) 到达 (2n,0) 且不越过 x 轴。这个和我们上面的那个问题是等价的，通过关于 y=−1 对称可以得到相同的答案。

当然，如果遇到等价于我们最初提到的问题的问题，那么也是可以考虑卡特兰数列的。

我们看一些例子来判断一下：

1.有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票，另外 n 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？

每有一个有 5 元的人进来，就多可以接一个 10 元的人，分别抽象成左右括号，那么符合卡特兰数列。

2.一个栈，加入顺序为 1,2,...,n ，问合法出栈顺序的方案数。

左右括号分别代表入栈和出栈，符合卡特兰数列。

3.n 个节点，可以构成多少不同的二叉树？

假设 n 个节点的答案为 h(n)

于是我们每次固定根节点，有 h(n)=∑ni=1h(i−1)h(n−i)

满足递归公式，符合卡特兰数列。

4.在圆上选择 2n 个点，求将这些点成对连接起来使得所得到的 n 条线段不相交的方案数。

选择两个点后其他点被分为两个部分，两边相互独立可以分治进行，满足递归公式，符合卡特兰数列。

5.对角线不相交的情况下，求将一个凸 2n 边形区域分成三角形区域的方案数。

这个和 4 的本质相同，就不再赘述。

例题

例题1

[NOIP2003 普及组] 栈

直接上公式就过了。

例题2

[HNOI2009]有趣的数列

分析一下可以发现是卡特兰数列。我们可以发现一个结论，在奇数位放置一个数，那么它之前的数都小于它，它之后的数都大于他。然后可以分治处理，且当只有一个奇数位时，方案只有一个，因此满足卡特兰数列。

然后考虑怎么求这个卡特兰数，由于模数随机，我们不能逆元，递推公式就用不了了。

递归公式复杂度是 O(n2) 的，显然不行。

那么只能考虑用通项公式求解。

(2nn)n+1=∏2ni=n+2i∏ni=1i

把上下两个数约分一下。具体是把分子分母拆成乘法形式，开数组打个标记表示有多少个这个因数，然后它这些因数继续拆成质因数，最后统一计算每个系数即可。因为卡特兰数必定是整数，因此不用担心约分约不干净的情况。

这个可以增长一下经验，放个代码：

int n,mods;
inline int inc(int x,int y){
    return (x+=y)>=mods?x-mods:x;
}
inline int dec(int x,int y){
    return (x-=y)<0?x+mods:x;
}
inline int mul(int x,int y){
    return 1ll*x*y%mods;
}
const int N=1e6+3;
int smallest[2*N];
std::vector<int>pri;
inline void Euler(){
    smallest[1]=1;
    for(int i=2;i<=2*n;++i){
        if(!smallest[i]){
            pri.push_back(i);
            smallest[i]=i;
        }
        for(auto it:pri){
            if(it*i>2*n) break;
            smallest[i*it]=it;
            if(i%it==0){
                break;
            }
        }
    }
}
int cnt[2*N];
inline int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=mul(ans,a);
        a=mul(a,a);
        b>>=1;
    }
    return ans;
}
int main(){
    filein(a);fileot(a);
    read(n,mods);
    for(int i=1;i<=n;++i)
        cnt[i]-=1;//分子
    for(int i=n+2;i<=2*n;++i)
        cnt[i]+=1;//分母
    Euler();
    for(int i=2*n;i>1;--i){
        if(smallest[i]<i){
            cnt[smallest[i] ]+=cnt[i];
            cnt[i/smallest[i] ]+=cnt[i];
        }
    }
    int ans=1;
    for(int i=2;i<=2*n;++i){
        if(cnt[i] and smallest[i]==i)
            ans=mul(ans,qpow(i,cnt[i]) );
    }
    printf("%d\n",ans);
    return 0;
}

斯特林数（Stirling）

第二类斯特林数

记作 {nk} ，或者 s2(n,k) 。表示 n 个两两不同的元素划分为 k 个互不区分的非空子集的方案数。

递推公式

{nk}={n−1k−1}+k{n−1k}

初始状态 {n0}=[n=0] 。

证明：

考虑新加入一个元素。

如果这个元素放在已经存在的非空子集中，有 k{n−1k} 种方案。

如果这个元素单独新开一个非空子集，有 {n−1k−1} 种方案。

然后加法原理合并可得。Q.E.D.

通项公式

{nk}=k∑i=0(−1)k−iini!(k−i)!

证明：

设 g(i) 为将 n 个不同元素放入 i 个不同集合中（可以为空集）的方案数，f(i) 为将 n 个不同元素放入 i 个不同集合（不可为空集）的方案数。

那么

g(i)=ing(i)=i∑j=0(ij)f(j)

第二个式子成立，是因为集合互不相同，先枚举启用几个集合，再枚举选择具体用哪些集合。

通过二项式反演：

f(i)=i∑j=0(−1)i−j(ij)g(j)=i∑j=0(−1)i−j(ij)jn=n∑i=0i!(−1)i−jjnj!(i−j)!

于是有

{nk}=f(k)k!=k∑i=0(−1)k−iini!(k−i)!

同行计算

发现是一个卷积的形式，f(x)=∑ni=0(−1)ii!xi 卷积 g(x)=∑ni=0ini! 即可 O(nlogn) 的时间内求出。

第一类斯特林数

记作 [nk] 或 s(n,k) 。表示 n 个不同的元素划分为 k 个不同的非空轮换的方案数。

什么叫做轮换？相等于一个首尾相接的环。也就是说，对于轮换 [A,B,C] ，其满足 [A,B,C]=[C,A,B]=[B,C,A]。

递推公式

[nk]=[n−1k−1]+(n−1)[n−1k]

初始状态 [nk]=[n=0]

证明：

还是考虑新加入一个元素。

如果单独开一个轮换，那么有方案数 [n−1k−1] 种。

如果加入一个已经存在的轮换，那么可以考虑加在已经存在的数后面，有 (n−1)[n−1k] 种方案数。然后加法原理合并即可。

Q.E.D.

然后似乎没有什么好用的通项公式？

上升幂和下降幂

上升幂 x¯n=∏n−1i=0(x+i)

下降幂 xn_=x!(x−n)!=∏n−1i=0(x−i)

上升幂转普通幂

x¯n=n∑i=0[ni]xi

证明：

考虑归纳证明：

n=0 时，等式两边皆为 1,等式成立

n=1 时，等式左边等于 x ，等式右边等于 x ，等式成立。

x¯n+1=(x+n)x¯n=(x+n)n∑i=0[ni]xi=xn∑i=0[ni]xi+nn∑i=0[ni]xi=n+1∑i=1[ni−1]xi+nn+1∑i=0[ni]xi=n+1∑i=0([ni−1]+n[ni])xi=n+1∑i=0[n+1i]xi

Q.E.D.

衍生公式：

由上式加上斯特林反演得

xn=n∑i=0{ni}(−1)n−ix¯i

下降幂转普通幂

xn_=n∑i=0[nk](−1)n−ixi

证明：

同样考虑归纳证明：

n=0 时，等式两边皆为 1 ，等式成立

n=1 时，等式两边皆为 x ，等式成立

xn+1_=(x−n)xn_=(x−n)n∑i=0[ni](−1)n−ixi=xn∑i=0[ni](−1)n−ixi−nn∑i=0[ni](−1)n−ixi=n∑i=0[ni](−1)n−ixi+1−nn∑i=0[ni](−1)n−ixi=n+1∑i=1[ni−1](−1)n−i+1xi−nn+1∑i=0[ni](−1)n−ixi=n+1∑i=1[ni−1](−1)n−i+1xi+nn+1∑i=0[ni](−1)n−i+1xi=n+1∑i=0([ni−1]+n[ni])(−1)n−i+1xi=n+1∑i=0[n+1i](−1)n−i+1xi=n+1∑i=0[n+1i](−1)(n+1)−ixi

Q.E.D.

衍生公式：

同样是由上式加上斯特林反演得

xn=n∑i=0{ni}xi_

其实这个式子也可以不用斯特林反演，我们直接按照组合意义来证明。

证明：

mn=m∑i=0{ni}i!(mi)=m∑i=0{ni}mi_

这是因为 mn 的组合意义是将 n 个有区别的数放入 m 个有区别的集合，允许空集的方案数。上式子相当于先枚举盒子的个数，再枚举盒子的区别，再从 m 个集合中选出 i 个，然后再数放入。

当我们用这个来证明反演：

xn=n∑i=0{ni}xi_

这里枚举范围可以取 n 的原因是我们认为 i 大于 n 时，式子值为 0。

而大于 x 的部分，(xi) 取 0 ，因此得到此式。

Q.E.D.

一个小小结论，按上面两个式子拆解易证：

x¯n=(−1)n(−x)n_,xn_=(−1)n(−x)¯n

反转公式

n∑i=m(−1)n−i{ni}[im]=[m=n]

n∑i=m(−1)m−i[ni]{im}=[m=n]

反转公式（1）证明：

xn_=n∑i=0[ni](−1)n−ixi=n∑i=0[ni](−1)n−ii∑j=0{ij}xj_=n∑i=0xi_n∑j=i(−1)n−j[nj]{ji}

Q.E.D.

反转公式（2）证明：

n∑i=0{ni}xi_=n∑i=0{ni}(−1)i(−x)¯i=n∑i=0{ni}(−1)ii∑j=0[ij](−x)j=∑i=0xin∑j=i(−1)i−j{nj}[ji]

Q.E.D.

斯特林反演

f(n)=n∑i=0{ni}g(i)⇔g(N)=n∑i=0(−1)n−i[ni]f(i)

上式中一二类斯特林数可以互换位置。

证明：

已知： g(n)=∑ni=0(−1)n−i[ni]f(i)

f(n)=∑i=0[i=n]f(i)=n∑i=0n∑j=i{nj}[ji](−1)j−if(i)=n∑i=0{ni}i∑j=0(−1)i−j[ij]f(j)=n∑i=0{ni}g(i)

Q.E.D.

参考文献

二项式反演证明

min-max 容斥证明

浅谈斯特林数及斯特林反演