0.前要:
对称公式:
\mathrm{C}_{n}^{k}=\mathrm{C}_{n}^{n - k}
组合数递推公式:
\mathrm{C}_{n + 1}^{m}=\mathrm{C}_{n}^{m}+\mathrm{C}_{n}^{m - 1} (杨辉三角)
1.来源:一道模拟题的组合恒等式多选题
11.下列等式中正确的是( )
A.
\sum_{k = 1}^{8} \mathrm{C}_{8}^{k}=2^{8}
B.
\sum_{k = 2}^{8} \mathrm{C}_{k}^{2}=\mathrm{C}_{9}^{3}
C.
\sum_{k = 2}^{8} \frac{k - 1}{k!}=1-\frac{1}{8!}
D.
\sum_{k = 0}^{8} (\mathrm{C}_{8}^{k})^{2}=\mathrm{C}_{16}^{8}
答案:BCD
上题得到的一些高中求和形式的组合恒等式:
A.
\(\sum_{k = 0}^{n}\mathrm{C}_{n}^{k}=2^{n}\)
proof: 对于二项式
\((a + b)^n=\sum_{k = 0}^{n}\binom{n}{k}a^{n - k}b^{k}\) ,当
\(a=b = 1\) 时,有
\((1 + 1)^n=\sum_{k = 0}^{n}\binom{n}{k}\)
即
\(\sum_{k = 0}^{n}\mathrm{C}_{n}^{k}=2^{n}\)
B.
\(\sum_{k = r}^{n}\mathrm{C}_{k}^{r}=\mathrm{C}_{n + 1}^{r+1}\)
proof: 由组合数递推公式:
\mathrm{C}_{n + 1}^{m}=\mathrm{C}_{n}^{m}+\mathrm{C}_{n}^{m - 1}
\begin{align*} C_{k}^{a} + C_{k}^{a + 1} &= \cancel{C_{k + 1}^{a + 1}} \\ \cancel{C_{k + 1}^{a + 1}} + C_{k + 1}^{a} &= \cancel{C_{k + 2}^{a + 1}} \\ \cancel{C_{k + 2}^{a + 1}} + C_{k + 2}^{a} &= \cancel{C_{k + 3}^{a + 1}} \\ &\vdots \\ \cancel{C_{n}^{a + 1}} + C_{n}^{a} &= C_{n + 1}^{a + 1} \end{align*}
求和后,即
\sum_{i = k}^{n} C_{i}^{a} + C_{k}^{a + 1} = C_{n + 1}^{a + 1}\
或者更清晰的,
\large \begin{aligned} & \quad\quad\quad\quad\color{blue}{C_{k}^{a + 1}} \quad + \quad C_{k}^{a} \quad + \quad C_{k + 1}^{a} \quad + \quad \cdots \quad + \quad C_{n}^{a}\\ & \quad\quad\quad\quad\quad\downarrow \quad \quad \scriptstyle{\text{合并前两项}} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\\ & \quad\quad\quad\quad\quad\color{green}{C_{k + 1}^{a + 1}} \quad\quad + \quad C_{k + 1}^{a} \quad + \quad \cdots \quad + \quad C_{n}^{a}\\ & \quad\quad\quad\quad\quad\quad\downarrow \quad \quad \scriptstyle{\text{继续合并}} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\\ & \quad\quad\quad\quad\quad\quad\color{green}{C_{k + 2}^{a + 1}} \quad\quad\quad + \quad \cdots \quad + \quad C_{n}^{a}\\ & \quad\quad\quad\quad\quad\quad\quad\downarrow \quad \quad \scriptstyle{\quad \ \ \ \vdots} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\\ & \quad\quad\quad\quad\quad\quad\quad\color{green}{C_{n}^{a + 1}} \quad\quad\quad\quad\quad + \quad C_{n}^{a}\\ & \quad\quad\quad\quad\quad\quad\quad\quad\downarrow \quad \quad \scriptstyle{\text{最终合并}} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\\ & \quad\quad\quad\quad\quad\quad\quad\quad\color{red}{C_{n + 1}^{a + 1}} \end{aligned}
\sum_{i = k}^{n} \mathrm{C}_{i}^{a} + \mathrm{C}_{k}^{a + 1} = \boxed{\color{red}{\mathrm{C}_{n + 1}^{a + 1}}}
\large \begin{aligned} & \quad\quad\quad\quad\color{blue}{\binom{k}{a + 1}} \quad + \quad \binom{k}{a} \quad + \quad \binom{k + 1}{a} \quad + \quad \cdots \quad + \quad \binom{n}{a} \\ & \quad\quad\quad\quad\quad\downarrow \quad \quad \scriptstyle{\text{合并前两项}} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \\ & \quad\quad\quad\quad\quad\color{green}{\binom{k + 1}{a + 1}} \quad\quad + \quad \binom{k + 1}{a} \quad + \quad \cdots \quad + \quad \binom{n}{a} \\ & \quad\quad\quad\quad\quad\quad\downarrow \quad \quad \scriptstyle{\text{继续合并}} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \\ & \quad\quad\quad\quad\quad\quad\color{green}{\binom{k + 2}{a + 1}} \quad\quad\quad + \quad \cdots \quad + \quad \binom{n}{a} \\ & \quad\quad\quad\quad\quad\quad\quad\downarrow \quad \quad \scriptstyle{\quad \ \ \ \vdots} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \\ & \quad\quad\quad\quad\quad\quad\quad\color{green}{\binom{n}{a + 1}} \quad\quad\quad\quad\quad + \quad \binom{n}{a} \\ & \quad\quad\quad\quad\quad\quad\quad\quad\downarrow \quad \quad \scriptstyle{\text{最终合并}} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \\ & \quad\quad\quad\quad\quad\quad\quad\quad\color{red}{\binom{n + 1}{a + 1}} \end{aligned}
C.
\(\frac{k - 1}{k!}=\frac{k}{k!}-\frac{1}{k!}=\frac{1}{(k - 1)!}-\frac{1}{k!}\) 阶乘裂项
我们有求和:
\sum_{k = 2}^{n}\frac{k - 1}{k!}=\sum_{k = 2}^{n}(\frac{1}{(k - 1)!}-\frac{1}{k!})=( \frac{1}{1!}-\frac{1}{2!})+(\frac{1}{2!}-\frac{1}{3!})+\cdots+(\frac{1}{(n - 1)!}-\frac{1}{n!})=\boxed{1-\frac{1}{n!}}
D.
\sum_{k = 0}^{r}\mathrm{C}_{m}^{k}\mathrm{C}_{n}^{r - k}=\mathrm{C}_{m + n}^{r}
其中等式运用到:“ 当
m > n 时,规定
\mathrm{C}_{n}^{m}=0 ”,以满足求和下的组合数“越界”
或对于
n\in N^{*}\ ,有
\boxed{\sum_{k = 0}^{n} \left( \mathrm{C}_{n}^{k} \right)^2=\mathrm{C}_{2n}^{n}} ,此时任意
n ,
k 的取值不再“越界”
分类事件下的组合恒等式意义:
右边
C_{2n}^{n} 表示从
2n 个元素中选取
n 个元素的方法数。将
2n 个元素均分为两组,每组
n 个。
从第一组选
n 个元素,从第二组选
n - k 个元素
( k = 0, 1, \dots, n ) ,则总方法数为
\sum_{k=0}^{n} C_{n}^{k}C_{n}^{n - k} 。由于
C_{n}^{n - k} = C_{n}^{k} ,故
\sum_{k=0}^{n} C_{n}^{k}C_{n}^{n - k} = \sum_{k=0}^{n} \left( C_{n}^{k} \right)^2 ,它与
C_{2n}^{n} 计数的是同一事件,因此等式成立。
代数化的证明(比较系数、算两次方法):
proof: 利用二项式定理:
(1 + x)^{2n} = \sum_{r=0}^{2n} C_{2n}^{r} x^{r} 其中
x^{n} 的系数为
C_{2n}^{n}
同时,
(1 + x)^{2n} = (1 + x)^{n} \cdot (1 + x)^{n}。将 (1 + x)^{n} 展开为
\sum_{i=0}^{n} C_{n}^{i} x^{i} ,则:
(1 + x)^{n} \cdot (1 + x)^{n} = \left(\sum_{i=0}^{n} C_{n}^{i} x^{i}\right)\left(\sum_{j=0}^{n} C_{n}^{j} x^{j}\right)
或者,更直白地
\left(\sum_{j=0}^{n} C_{n}^{j} x^{j}\right) 可以写成
\left(\sum_{j=0}^{n} C_{n}^{n-j} x^{n-j}\right)
即
(1 + x)^{n} \cdot (1 + x)^{n} = \left(\sum_{i=0}^{n} C_{n}^{i} x^{i}\right)\left(\sum_{i=0}^{n} C_{n}^{n-i} x^{n-i}\right) 对两个括号内的每个
i 两两配对乘积并求和
可知其中
x^{n} 的系数为
\sum_{k=0}^{n} C_{n}^{k} C_{n}^{n - k} 。由于
C_{n}^{n - k} = C_{n}^{k} ,故该系数为
\sum_{k=0}^{n} (C_{n}^{k})^2
因此:
\sum_{k=0}^{n} (C_{n}^{k})^2 = C_{2n}^{n}
□.
也可由范德蒙德卷积公式
\sum_{k=0}^{r} C_{m}^{k}C_{n}^{r - k} = C_{m + n}^{r} ,令
m = n = r 直接得到。
这就是下面我们给出对D选项涉及的恒等式的推广:
3.范德蒙德卷积公式
\sum_{k = 0}^{r}\binom{m}{k}\binom{n}{r - k}=\binom{m + n}{r}
即
\sum_{k=0}^{r} C_{m}^{k}C_{n}^{r - k} = C_{m + n}^{r}
对于证明,我们可以同上方法用组合分类进行直观理解,也可以同上运用代数上比较系数的方法进行推导
我们现在给出代数证明:
proof :同样借助二项式定理,考虑
(1 + x)^{m + n} = (1 + x)^{m} (1 + x)^{n} 。
左边展开:
(1 + x)^{m + n} = \sum_{r=0}^{m + n} C_{m + n}^{r} x^{r} 。
右边展开:
(1 + x)^{m} = \sum_{i=0}^{m} C_{m}^{i} x^{i},(1 + x)^{n} = \sum_{j=0}^{n} C_{n}^{j} x^{j} 。
两式相乘后,
x^{r} 的系数为
\sum_{k=0}^{r} C_{m}^{k} C_{n}^{r - k}(令 i = k,j = r - k,则 i + j = r)
比较两边
x^{r} 的系数,可得:
\boxed{\mathrm{C}_{m + n}^{r}=\sum_{k = 0}^{r}\mathrm{C}_{m}^{k}\mathrm{C}_{n}^{r - k}}
这就完成了范德蒙德卷积公式的证明.
\Huge\color{red}{其他部分待更新}
4.其他关于二项式定理
伯努利不等式特殊形式
(
n 为正整数)当
\(x\gt - 1\) 时,
\((1 + x)^n\geq1 + nx\) 。当且仅当
\(n = 1\) 或
x = 0 时等号成立。
* 一般形式:若
\(x_1,x_2,\cdots,x_n\) 同号且
\(x_i\gt - 1\) ,
\(i = 1,2,\cdots,n\) ,则
(1 + x_1)(1 + x_2)\cdots(1 + x_n)\geq1 + x_1 + x_2+\cdots+x_n
最大系数问题
由于考题经常出二项式的最大系数值或项问题,我们现在讨论一般情况
只需考虑
(1+p)^n ,
p>0 ,这是因为其他情况只需倍扩即可
由离散性或“单峰性”(这个可以通过比值存在唯一"1"点保证,与导函数零点类似,因此必然存在单峰性),
我们可以通过相邻项比值(差值同理)的单调性分析,推导其最大系数项的位置及唯一性。
相邻项比值与不等式组 相邻两项的比值为:
\frac{a_k}{a_{k-1}} = \frac{\mathrm{C}_n^k p^k}{\mathrm{C}_n^{k-1} p^{k-1}} = \frac{(n-k+1)p}{k} \quad (k \geq 1).
若
a_k\ 是最大系数项,则需满足:
\[ \begin{cases} a_k \geq a_{k-1} \quad \text{(不小于前一项)} \\ a_k \geq a_{k+1} \quad \text{(不小于后一项)} \end{cases} \]
二、解不等式确定
k 的范围
由
a_k \geq a_{k-1}(前一项不大于当前项) :
\frac{(n-k+1)p}{k} \geq 1 \implies k \leq \frac{(n+1)p}{1+p}. \quad \text{(右边界由此不等式得到)} 由
a_k \geq a_{k+1}(后一项不大于当前项) :
考虑
a_{k+1} = \mathrm{C}_n^{k+1} p^{k+1} ,则
\frac{a_{k+1}}{a_k} = \frac{(n-k)p}{k+1} \leq 1 \implies k \geq \frac{(n+1)p}{1+p} (左边界由此不等式得到)
的范围: ,区间为
\([x-1, x]\) ,长度为
\(1\) ,分两种情况:
1. 当 x 不是整数时: 区间内唯一整数为
\lfloor x \rfloor ,对应第
\lfloor x \rfloor + 1\ 项为最大系数项。
2. 当 x 是整数时(即 \(x = m \in \mathbb{N}\)): 区间端点 \(m-1\) 和 \(m\) 均为整数,此时 \(a_{m-1} = a_m\),即第 \(m\) 项和第 \(m+1\) 项系数相等,同为最大值。
设
m = \frac{(n+1)p}{1+p} , 若
m \notin \mathbb{Z} ,则最大系数项为第
\lfloor m \rfloor + 1 项; - 若
m \in \mathbb{Z} ,则第
\(m\) 项和第
m+1 项系数相等且最大。
整除问题
收录于知乎专栏「高中数学」· 查看知乎原文