二项式定理的一个推广

good1210 · 2025-12-27 10:40:47 · 算法·理论

声明

本文说明的推广由 ~~xxs~~@good1210 发现并利用数学归纳法证明。

:::align{center}

\textbf{Abstract}

本文简单讲解了二项式定理并在其基础上说明了二项式定理的一个推广，并对其进行证明。 :::

注：作者 @good1210 对中学数学没有系统性的学习，所以部分显而易见的东西会花费一点笔墨说明。并且部分描述可能也没说清楚。见谅。

组合数

在二项式定理之前，你需要知道组合数的概念。如果你已经了解，则这段内容可以跳过。

组合数可被写为 \displaystyle\binom{n}{k} 或 C_n^k 的形式。

表示在 n 个元素中选取互不相同的 k 个元素的方案数。

设集合 S=\{a_1,a_2,\cdots,a_n\} 有 n 个元素，其子集 T\subseteq S 含有 m 个元素（0\le m\le n）。

可用集合表达为：

C_{n}^{k}=|\{T\subseteq S:|S|=n, |T|=m\le n\}|

可以 DP 求解，代码如下：

#include <iostream>
#define int long long
using namespace std;

int n, m;
int dp[1005][1005];
// dp[n][k] 表示在 n 个元素中选取互不相同的 k 个元素的方案数

inline void solve(int n, int m) {
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= m; j++) {
            // 杨辉三角的性质、组合数递推公式，以后会说
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
        }
    }
    return;
}

signed main() {
    cin >> n >> m;
    solve(n, m);
    cout << dp[n][m];
    return 0;
}

二项式定理

首先你要知道二项式定理。

描述

二项式描述如下：

$$\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k$$ 即 $$(x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k$$ 其中 $n\in\mathbb{N^*}$。

证明

考虑使用数学归纳法证明。

:::info[数学归纳法] 数学归纳法是一种证明方式。

具体步骤：

证明命题在 n=n_0（其中 n,n_0\in\mathbb{N^*}）
假设命题当 n=m 时成立
证明命题在 n=m+1 时成立
命题在 n\ge n_0 时成立

关于数学归纳法更多内容可以看浅谈数学归纳法这篇文章，很充实。 :::

对于 n=1 的情况：

(x+y)^1=x+y\tag{1}

以及

\sum_{k=0}^{1}\binom{1}{k}x^{1-k}y^k=\binom{1}{0}x+\binom{1}{1}y=x+y\tag{2}

显然，式 (1) 与式 (2) 相等，即成立。

假设其在 n=m 时成立。

利用 (x+y) 乘上原式，得：

(x+y)\times\sum_{k=0}^{m}\binom{m}{k}x^{m-k}y^k\tag{3}

展开，得：

x\sum_{k=0}^{m}\binom{m}{k}x^{m-k}y^k+y\sum_{k=0}^{m}\binom{m}{k}x^{m-k}y^k\tag{4}

将对应的幂次增加：将 x\times x^{m-k} 合并为 x^{m-k+1}；将 y\times y^k 合并为 y^{k+1}。则得：

\sum_{k=0}^{m}\binom{m}{k}x^{m-k+1}y^k+\sum_{k=0}^{m}\binom{m}{k}x^{m-k}y^{k+1}\tag{5}

将 x^{m-k+1} 改为 x^{m+1-k}，等价于式 (5)。为：

\sum_{k=0}^{m}\binom{m}{k}x^{m+1-k}y^k+\sum_{k=0}^{m}\binom{m}{k}x^{m-k}y^{k+1}\tag{6}

为了使得其能够被合并为相同的形式，我们必须做到：

两个式子中，关于 x 和 y 的指数互相一致；
大 \sum 式子的上指标、下指标互相一致。
其中 x 的指数为 m+1-k，y 的指数为 k。

所以，我们需要调整变量 \bm k 的范围（显然，你不调整就不能合并）。

具体地，见下面的过程。

我们首先将部分标号：

\underset{\text{Part I}}{\underbrace{\sum_{k=0}^{m}\binom{m}{k}x^{m+1-k}y^k}}+\underset{\text{Part II}}{\underbrace{\sum_{k=0}^{m}\binom{m}{k}x^{m-k}y^{k+1}}}

我们将 \text{Part I} 与 \text{Part II} 作比较，它们只是 k 的上下指标相同，所以调整 k。

对于 \text{Part I}，采取不变，因为 x 和 y 已经满足。

对于 \text{Part II}，观察到：

m-(k-1)=m-k+1=m+1-k
(k-1)+1=k

所以我们将 \text{Part II} 中的 k 的上下指标同时加 \bm{1}，得

\underset{\text{Part I}}{\underbrace{\sum_{k=0}^{m}\binom{m}{k}x^{m+1-k}y^k}}+\underset{\text{Part II}}{\underbrace{\sum_{k=1}^{m+1}\binom{m}{k-1}x^{m+1-k}y^{k}}} \tag{7}

现在关于 x 和 y 的指数一致了，但是大 \sum 式子的上指标、下指标还不一致。

考虑将两个大 \sum 式子的下指标取 \max(0,1)=1，上指标取 \min(m,m+1)=m，并将其余项排出，得

x^{m+1}+\underset{\text{Part I}}{\underbrace{\sum_{k=1}^{m}\binom{m}{k}x^{m+1-k}y^k}}+\underset{\text{Part II}}{\underbrace{\sum_{k=1}^{m}\binom{m}{k-1}x^{m+1-k}y^{k}}}+y^{m+1} \tag{8}

现在，\text{Part I} 与 \text{Part II} 的 k 的上下指标一致了，那么合并：

x^{m+1}+\sum_{k=1}^{m}\left[\binom{m}{k}+\binom{m}{k-1}\right]x^{m+1-k}y^k+y^{m+1} \tag{9}

根据上面的公式，变为：

x^{m+1}+\sum_{k=1}^{m}\binom{m+1}{k}x^{m+1-k}y^k+y^{m+1} \tag{10}

观察到：

所以可以再次合并，得

\sum_{k=0}^{m+1}\binom{m+1}{k}x^{m+1-k}y^k \tag{11}

若用 n 替换 m+1，则

\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k\tag{12}

所以 n=m+1 时成立。

所以对于任意的正整数 n 都成立。

二项式定理得证。

我的推广

由来

一天，一个 xxs（good1210）在研究方程通解，试图观察多项式的特征以及展开式然后因式分解得到结果。

于是开始枚举：

x+a_1=x+a_1

(x+a_1)\times(x+a_2)=x^2+(a_1+a_2)x+a_1a_2

(x+a_1)\times(x+a_2)\times(x+a_3)=x^3+(a_1+a_2+a_3)x^2+(a_1a_2+a_1a_3+a_2a_3)x+a_1a_2a_3

剩下的就不枚举了。

可以发现系数与 x 的次数有关，然后就是开始总结、归纳、证明。

但是最终~~还是失败了~~。

描述

$$\sum_{k=0}^{n}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le n}\prod_{j=1}^{k}a_{i_j}\right)x^{n-k}$$ 即 $$\prod_{i=1}^{n}\left(x+a_i\right)=\sum_{k=0}^{n}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le n}\prod_{j=1}^{k}a_{i_j}\right)x^{n-k}$$ 其中 $n\in\mathbb{N^*}$。

证明

还是利用数学归纳法。

对于 n=1：

\prod_{i=1}^{1}\left(x+a_i\right)=x+a_1\tag{13}

以及

\sum_{k=0}^{1}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le 1}\prod_{j=1}^{k}a_{i_j}\right)x^{1-k}=x+a_1\tag{14}

式 (13) 与式 (14) 相等，所以 n=1 时成立。

假设 n=m 时成立。

令原式乘上新的二项式 (x+a_{m+1})，得

(x+a_{m+1})\times\sum_{k=0}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}\right)x^{m-k}\tag{15}

得

x\sum_{k=0}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}\right)x^{m-k}+a_{m+1}\sum_{k=0}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}\right)x^{m-k}\tag{16}

与证明二项式定理一样的，将 x\times x^{m-k} 变为 x^{m-k+1}，将 a_{m+1} 放入第二个大 \sum 式子里，得

\sum_{k=0}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}\right)x^{m-k+1}+\sum_{k=0}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}\right)a_{m+1}x^{m-k}\tag{17}

调整一下 x^{m-k+1} 为 x^{m+1-k}，得

\sum_{k=0}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}\right)x^{m+1-k}+\sum_{k=0}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}\right)a_{m+1}x^{m-k}\tag{18}

现在，需要做的是：

统一上式 \bm x 的系数；
统一大 \bm{\sum} 式子的上指标、下指标。
合并两个大 \bm{\sum} 式子。

首先，x^{m+1-k} 是我们想要的形式，为了让 x^{m-k} 得到 x^{m+1-k}，令 \bm k 的上指标、下指标同时增加 \bm 1，则此时原式中 \bm k 为了保持大小不变需要减去 \bm 1。

得

\sum_{k=0}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}\right)x^{m+1-k}+\sum_{k=1}^{m+1}\left(\sum_{1\le i_1<i_2<\cdots<i_{k-1}\le m}\prod_{j=1}^{k-1}a_{i_j}\right)a_{m+1}x^{m+1-k}\tag{19}

现在，x 的系数已经被统一了，考虑统一大 \bm{\sum} 式子的上指标、下指标。

方法还是上指标取 \min(m,m+1)=m，下指标取 \max(0,1)=1，其余项排出。

得

x^{m+1}+\sum_{k=1}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}\right)x^{m+1-k}+\sum_{k=1}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_{k-1}\le m}\prod_{j=1}^{k-1}a_{i_j}\right)a_{m+1}x^{m+1-k}+a_1a_2\cdots a_{m+1}\tag{20}

处理一下细节，将第二部分大 \sum 式子中的 a_{m+1} 移至括号内的大 \sum 式子的右边（大 \prod 式子的左边），得

x^{m+1}+\sum_{k=1}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}\right)x^{m+1-k}+\sum_{k=1}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_{k-1}\le m}a_{m+1}\times\prod_{j=1}^{k-1}a_{i_j}\right)x^{m+1-k}+a_1a_2\cdots a_{m+1}\tag{21}

现在将两个大 \sum 式子合并，得

x^{m+1}+\sum_{k=1}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}+\sum_{1\le i_1<i_2<\cdots<i_{k-1}\le m}a_{m+1}\times\prod_{j=1}^{k-1}a_{i_j}\right)x^{m+1-k}+a_1a_2\cdots a_{m+1}\tag{22}

现在的问题就是如何合并中间括号的内容？

我们不妨解析一下括号内的部分：

式 \displaystyle\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}（记为 \text{Part I}）即从 m 个元素中挑选 k 个互不相同的元素，并将每一种挑选结果的 k 个元素相乘，并求和。
式 \displaystyle\sum_{1\le i_1<i_2<\cdots<i_{k-1}\le m}a_{m+1}\times\prod_{j=1}^{k-1}a_{i_j}（记为 \text{Part II}）即从 m 个元素中挑选 k-1 个互不相同的元素，并将每一种挑选结果的 k-1 个元素相乘的结果再与 a_{m+1} 相乘，并求和。

我们做出一个统一，分别等价于

两者结合即为：

:::align{center} 从 a_1,a_2,\cdots,a_m,a_{m+1} 中选取 k 个互不相同的元素 :::

即

\sum_{1\le i_1<i_2<\cdots<i_{k}\le m+1}\prod_{j=1}^{k}a_{i_j}

同时，\text{Part I} 的乘积结果的数量即 \displaystyle\binom{m}{k}，\text{Part II} 的乘积结果的数量即 \displaystyle\binom{m}{k-1}，两者相加即为 \displaystyle\binom{m+1}{k}，正是我们得到的结果中的乘积结果的数量！

至此，我们也相当于证明了

\binom{m}{k}+\binom{m}{k-1}=\binom{m+1}{k}

这个恒等式。

回到正题，我们现在已经得到了：

\left(\sum_{1\le i_1<i_2<\cdots<i_k\le m}\prod_{j=1}^{k}a_{i_j}\right)+\left(\sum_{1\le i_1<i_2<\cdots<i_{k-1}\le m}a_{m+1}\times\prod_{j=1}^{k-1}a_{i_j}\right)=\sum_{1\le i_1<i_2<\cdots<i_{k}\le m+1}\prod_{j=1}^{k}a_{i_j}

那么式 (22) 等于

x^{m+1}+\sum_{k=1}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_{k}\le m+1}\prod_{j=1}^{k}a_{i_j}\right)x^{m+1-k}+a_1a_2\cdots a_{m+1}\tag{23}

现在，解析一下大 \sum 式外的两个单项式：

现在，合并两个式子，即

\left(\sum_{1\le i_1<i_2<\cdots<i_{0}\le m+1}\prod_{j=1}^{0}a_{i_j}\right)x^{m+1-k}+\sum_{k=1}^{m}\left(\sum_{1\le i_1<i_2<\cdots<i_{k}\le m+1}\prod_{j=1}^{k}a_{i_j}\right)x^{m+1-k}+\displaystyle\left(\sum_{1\le i_1<i_2<\cdots<i_{m+1}\le m+1}\prod_{j=1}^{m+1}a_{i_j}\right)x^{m+1-(m+1)}\tag{24}

可得

\sum_{k=0}^{m+1}\left(\sum_{1\le i_1<i_2<\cdots<i_{k}\le m+1}\prod_{j=1}^{k}a_{i_j}\right)x^{m+1-k}\tag{25}

将 n=m+1 代入，得

\sum_{k=0}^{n}\left(\sum_{1\le i_1<i_2<\cdots<i_{k}\le n}\prod_{j=1}^{k}a_{i_j}\right)x^{n-k}\tag{26}

这样我们就得到了一开始的形式。

所以在 n=m 成立时，n=m+1 也同样成立。

所以 \textbf{Theorem 2} 对于任意正整数 n 都成立。

得证。

手稿

以下是证明的手稿，图片较大所以折叠了。

:::success[证明的手稿]

图片比较大，加载可能比较慢。

~~是我写的 qwq~~ :::

手稿可能有不对的地方。

特殊形式

当且仅当 a_1=a_2=\cdots=a_n=y 时，原式变为：

\sum_{k=0}^{n}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le n}\prod_{j=1}^{k}y\right)x^{n-k}\tag{27}

即

\sum_{k=0}^{n}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le n}y^k\right)x^{n-k}\tag{28}

将 y^k 提出，得

\sum_{k=0}^{n}\left(\sum_{1\le i_1<i_2<\cdots<i_k\le n}1\right)x^{n-k}y^k\tag{29}

而中间的 \displaystyle\left(\sum_{1\le i_1<i_2<\cdots<i_k\le n}1\right) 即 \displaystyle\binom{n}{k}，则可得

\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k\tag{30}

式 (30) 即二项式定理。

所以当且仅当 a_1=a_2=\cdots=a_n 时，原式退化为二项式定理。

结语

感谢你能耐心看到这里，给个赞吧 QwQ。