1. 二项式转换#

给定一个数列 $a_n$, $n\geq s$ ，其二项式转换 $b_n$ , $n\geq s$ 定义如下：

$b_n=\sum_{k=s}^n \binom{n}{k} a_k$

其中， $\binom{n}{k}$ 表示从 $n$ 个不同的元素中选取 $k$ 个元素的组合数。从式子中可以看出，二项式转换的过程是将原数列 ${a_n}$ 的每一项乘以一系列二项式系数 $\binom{n}{k}$，并对所有系数相加得到 $b_n$。

2. 逆二项式转换#

给定一个数列 $b_n$ , $n\geq s$ ，其逆二项式转换 $a_n$, $n\geq s$ 定义如下：

$a_n=\sum_{k=s}^n (-1)^{n-k} \binom{n}{k} b_k$

逆二项式转换的过程是将原数列 ${b_n}$ 的每一项乘以一系列带符号的二项式系数 $(-1)^{n-k}\binom{n}{k}$，并对所有系数相加得到 $a_n$。

3. 二项式转换和逆二项式转换的性质#

• 二项式转换和逆二项式转换是可逆的

即对于任意数列 ${a_n}{n\geq s}$，有 ${a_n}$ 的二项式转换再进行逆二项式转换得到的数列仍为 ${a_n}$，即

$\text{逆二项式转换}(\text{二项式转换}({a_n}))={a_n}$

对于任意数列 ${b_n}{n\geq s}$，有 ${b_n}$ 的逆二项式转换再进行二项式转换得到的数列仍为 ${b_n}$，即

$\text{二项式转换}(\text{逆二项式转换}({b_n}))={b_n}$

• 二项式转换和逆二项式转换是线性变换

即对于任意数列 ${a_n}{n\geq s}$ 和 ${b_n}{n\geq s}$，以及任意常数 $\alpha,\ \beta$ ，有

$\text{二项式转换}(\alpha {a_n}+\beta {b_n})=\alpha (\text{二项式转换}({a_n}))+\beta (\text{二项式转换}({b_n}))$

$\text{逆二项式转换}(\alpha {a_n}+\beta {b_n})=\alpha (\text{逆二项式转换}{a_n}))+\beta (\text{逆二项式转换}({b_n}))$

1. 概念#

组合证明是一种通过不同方式计数同一组对象来证明恒等式的证明方法。它可以通过两种方式进行证明：双重计数证明和双射证明

2. 双重计数证明#

将恒等式左右两边所计数的对象表示为同一集合 $X$，但是以不同的方式计数，即 $L=|X|=R$。这意味着恒等式左右两边计数的对象数相同，因此它们是相等的。

3. 双射证明#

通过建立两个集合 $X$ 和 $Y$ 之间的一一映射（即双射）来证明恒等式左右两边计数的对象数相等，即 $L=|X|$，$R=|Y|$，并且存在一个双射 $f:X\to Y$。这意味着每个元素在 $L$ 中恰好对应于 $R$ 中的一个元素，并且每个元素在 $R$ 中恰好对应于 $L$ 中的一个元素。因此，它们是相等的。

4. 例证#

举个例子，考虑恒等式 $(n\mid r)=(n\mid (n-r))$，其中左边计数的是包含 $r$ 个 $0$ 的长度为 $n$ 的 $01$ 串的数量，右边计数的是包含 $n-r$ 个 $1$ 的长度为 $n$ 的 $01$ 串的数量。这里我们可以将这些 $01$ 串组成一个集合 $X$，并通过将一个 $01$ 串中的 $0$ 和 $1$ 进行交换，得到一个集合 $Y$。我们可以通过构造一个双射 $f:X\to Y$，其中 $f$ 将一个 $01$ 串中的 $0$ 和 $1$ 进行交换，来证明左右两边计数的对象数相等，即 $L=|X|$，$R=|Y|$，并且存在一个双射 $f:X\to Y$。因此，这个恒等式成立。