排列组合
2026-04-24
曲棍球棒定理
i=x∑n(xi)=(x+1n+1)
证明
由组合数学基本公式:(xi)=(x−1i)+(x−1i−1),可以将其中每一项拆开后按顺序合并即可。
二项式反演
二项式反演类似容斥原理的代数形式,一般用于从好求的计数推出不好求的计数。(怎么这么废话)
形式一
g(n)=i=0∑n(in)f(i)⟺f(n)=i=0∑n(in)(−1)n−ig(i)
我们假设有若干个条件,那么 f(i) 表示恰好满足 i 个条件的方案数、g(n) 表示满足若干个条件的总方案数。
推导过程
考虑将 g 带入右侧,进行代数变化得到二项式定理,所以:
i=0∑n(in)(−1)n−ii=0∑n(in)f(i)
交换求和次序,得到:
j=0∑nf(j)i=j∑n(−1)n−i(in)(ji)
将后面的组合数合并,并将与 i 无关的放到前面,得到:
j=0∑nf(j)(jn)i=j∑n(−1)n−i(i−jn−j)
注意到出现了很多 n−i、i−j 类似状物,考虑换元,令 k=i−j,则当 i∈[j,n] 时,k∈[0,n−j],则:
j=0∑nf(j)(jn)k=0∑n−j(−1)n−j−k(kn−j)
我们将内层提出一个 (−1)n−j,并使用二项式定理:
j=0∑nf(j)(jn)(−1)n−jk=0∑n−j(−1)k(kn−j)=j=0∑nf(j)(jn)(−1)n−j(1−1)n−j
注意到 (1−1)n−j 当且仅当 n=j 时为 1,否则为 0,所以整个求和只剩下 n=j 时的值,即:
(∗)=f(n)
原式得证。
形式二
g(n)=i=n∑N(ni)f(i)⟺f(n)=i=n∑N(−1)i−n(ni)g(i)
推导和上面类似,我就不写文字了。
推导过程
(∗)=i=n∑N(−1)i−n(ni)j=i∑N(ij)f(j)=j=n∑Nf(j)i=n∑j(−1)i−n(ni)(ij)=j=n∑Nf(j)(nj)i=0∑j−n(ij−n)(−1)i=j=n∑Nf(j)(nj)(−1)j−n=f(n)
