前言

前言

本讲义是“杨辉三角与组合恒等式”专题知识课的配套文字版,内容与课堂上使用的交互课件一一对应,共 5 章、20 个专题,覆盖组合数的意义与性质、杨辉三角中的行和与斜线和、带权求和、范德蒙德恒等式和二项式定理。

每个专题怎么读

每个专题自成一节,先给出核心公式和它在杨辉三角中的位置,再按课堂的四步展开:

  1. 观察规律:在三角形里找到公式涉及的格子,用具体数值看出规律;
  2. 计数解释:给公式两边各讲一个“数同一件事”的故事,理解它为什么成立;
  3. 推导证明:用代数方法严格证明;
  4. 应用辨析:说明公式的适用条件、常见误用和典型用法。

每节末尾有一道理解检查小题,答案与解析附在题后,建议先做再看。书中组合数记作 $\mathrm{C}_n^k$,约定 $n$ 为非负整数,整数 $k$ 越界时 $\mathrm{C}_n^k=0$,$0!=1$;三角形顶部为第 $0$ 行,每行下标从 $0$ 开始。

版式约定

思路与要点

浅紫色框:解题思路、关键观察、规律总结。

注意

浅黄色框:需要特别留意的条件和细节。

易错

浅红色框:常见错误与辨析。

结论卡

白底紫框:需要记住的公式与二级结论。

书中插图取自课堂交互课件中的动态图形,是某一时刻的静态画面,图注说明了图中各部分的含义。

专题 01

组合数的意义

从“选出一组”开始,理解杨辉三角中的每一个数。

核心公式

$$\mathrm{C}_{n}^{k}=\dfrac{n!}{k!\,(n-k)!}$$

$n$、$k$ 为整数,$0\le k\le n$。

杨辉三角第 0 至第 5 行:每格上方是数值,下方是组合数 \mathrm{C}_n^k;紫色格 \mathrm{C}_5^2=10 表示从 5 个不同元素中选 2 个的全部选法数。
图 1杨辉三角第 $0$ 至第 $5$ 行:每格上方是数值,下方是组合数 $\mathrm{C}_n^k$;紫色格 $\mathrm{C}_5^2=10$ 表示从 $5$ 个不同元素中选 $2$ 个的全部选法数。

一组无序的选择

从 5 个不同元素中选 2 个,入选人数始终为 2。

从 5 个不同元素中选 2 个:浅绿底与绿色描边的 1,2 入选,灰色的 3,4,5 未入选;这是一种无序选择。
图 2从 $5$ 个不同元素中选 $2$ 个:浅绿底与绿色描边的 $1,2$ 入选,灰色的 $3,4,5$ 未入选;这是一种无序选择。

图中示例选中 $\{1,2\}$,未选中 $\{3,4,5\}$。这里展示的只是一种具体选择;$\mathrm{C}_{5}^{2}=10$ 统计的是全部不同的选择。

观察规律:一个格子,一类选择

第 5 行、第 2 个下标处是 $\mathrm{C}_{5}^{2}$,表示从 5 个不同元素中选 2 个组成集合,有 10 种选法。

下标与行号

下标从 0 开始:第 $n$ 行共有 $n+1$ 个数。行号不等于从上往下数的行数。

计数解释:先区分“相加”与“相乘”

完成同一件事有互斥的不同类别,把各类方法数相加;一件事必须分几步完成,把各步方法数相乘。

先有序选出 $k$ 个元素,共 $n(n-1)\cdots(n-k+1)$ 种;同一组元素的 $k!$ 种次序都对应同一个组合。

推导证明:消去重复的顺序

$$ \begin{aligned} \mathrm{C}_{n}^{k}&=\dfrac{n(n-1)\cdots(n-k+1)}{k!}\\ &=\dfrac{n!}{k!\,(n-k)!} \end{aligned} $$

每个无序组合对应且恰好对应 $k!$ 个有序排列,所以除以 $k!$。

$\mathrm{C}_{n}^{0}=\mathrm{C}_{n}^{n}=1$:空集与全集各只有一种。约定 $0!=1$。

组合数的约定:$n$ 为非负整数;整数 $k$ 越界($k<0$ 或 $k>n$)时,$\mathrm{C}_{n}^{k}=0$。

应用辨析:看清题目是否区分位置

“选 3 人组成小组”只看成员;“选班长、副班长、学习委员”还区分职务,通常按排列计数。

注意

本讲讨论不同元素的不重复选取。允许重复、相同元素或圆排列时,不能直接套用这些公式。

课堂小测

课堂小测

从 5 人中选 2 人组成无职务差别的小组,有多少种?

查看答案与解析

答案A

解析

先选后排会重复计数,$5\times 4\div 2!=10$。

辨析
  • B:20 计入了先后次序,每组被数了 2 次
  • C:25 允许同一人被重复选入,不符合条件
  • D:5 没有覆盖所有两人组合。

相关专题:排列与组合;帕斯卡递推。

专题 02

排列与组合

先选后排:为什么排列数恰好是组合数的 $k!$ 倍?

核心公式

$$\mathrm{A}_{n}^{k}=k!\,\mathrm{C}_{n}^{k}=\dfrac{n!}{(n-k)!}$$

$n$、$k$ 为整数,$0\le k\le n$。

杨辉三角前 6 行(第 0 至 5 行),每格上方为数值,下方为对应的 \mathrm{C}_n^k;紫色高亮的是 \mathrm{C}_5^3=10。示例参数下 \mathrm{A}_{5}^{3}=3!\times\mathrm{C}_{5}^{3}=6\times10=60。
图 1杨辉三角前 6 行(第 0 至 5 行),每格上方为数值,下方为对应的 $\mathrm{C}_n^k$;紫色高亮的是 $\mathrm{C}_5^3=10$。示例参数下 $\mathrm{A}_{5}^{3}=3!\times\mathrm{C}_{5}^{3}=6\times10=60$。

同一组选人,可以排出不同次序

选定一组 3 人($A$、$B$、$C$),共有 $3!=6$ 种次序,全部列出如下:

第 1 种 第 2 种 第 3 种 第 4 种 第 5 种 第 6 种
$A\to B\to C$ $A\to C\to B$ $B\to A\to C$ $B\to C\to A$ $C\to A\to B$ $C\to B\to A$

每个无序组合都对应 $3!=6$ 个有序排列,所以 $10\times6=60$。

观察规律:选人之后,还要安排位置

从 5 人中选 3 人有 10 种;每组选出的人可排出 6 种次序。

计数解释:两条计数路径

  • 路径一:第一个位置有 $n$ 种选择,第二个位置有 $n-1$ 种,依次类推。
  • 路径二:先选出成员,再安排这 $k$ 人的次序。两步相乘。

推导证明:同一批有序结果,两种表达

$$\mathrm{A}_{n}^{k}=n(n-1)\cdots(n-k+1)=\mathrm{C}_{n}^{k}\,k!$$

排列与组合的换算,关键是每个无序组合都恰好对应 $k!$ 个排列。

应用辨析:职务、位置与顺序

有不同职务、名次、位置时,需要识别顺序;只选集合时无需顺序。

注意

“除以 $k!$”必须确认每种最终结果都恰好重复了 $k!$ 次,不能在有特殊限制时机械相除。

相关专题:组合数的意义;双重选取恒等式。

课堂小测

课堂小测

已知选出 3 人有 10 种方法,再让他们担任 3 个不同职务,有多少种?

查看答案与解析

答案A

解析

每组选人有 $3!=6$ 种任职方式,总共 $10\times6=60$。

辨析
  • B:3 个不同职务的安排数是 $3!$,不是 3。
  • C:10 只统计了成员,没有区分职务。
  • D:已选定的 3 人只有 $3!=6$ 种安排。
专题 03

对称性与互补选择

选中的人与未选中的人,描述的是同一种选择。

核心公式

$$ \mathrm{C}_{n}^{k}=\mathrm{C}_{n}^{n-k} $$

$n$、$k$ 为整数,$0\le k\le n$。

杨辉三角第 8 行中,绿色格表示选出的 3 人,橙色格表示留下的 5 人;两个格子的数均为 56,即 \mathrm{C}_{8}^{3}=\mathrm{C}_{8}^{5}=56。
图 1杨辉三角第 $8$ 行中,绿色格表示选出的 $3$ 人,橙色格表示留下的 $5$ 人;两个格子的数均为 $56$,即 $\mathrm{C}_{8}^{3}=\mathrm{C}_{8}^{5}=56$。

选中与留下,一一对应

用具体对象理解计数:把 $8$ 人依次编号为 $1,2,3,4,5,6,7,8$。例如,选中者为 $\{1,2,3\}$,未选中者为 $\{4,5,6,7,8\}$,后者是前者在这 $8$ 人中的补集。

这是一种具体选择;$\mathrm{C}_{8}^{3}=56$ 统计全部不同选择。

观察规律:一行中的镜像

下标 $3$ 与 $5$ 关于行中央对称,两格的数都是 $56$。

计数解释:从一个集合到它的补集

给定选中的 $k$ 人,未选中的 $n-k$ 人就被唯一确定;反过来也成立。两个选择集合之间存在一一对应,所以数量相同。

推导证明:阶乘式也揭示对称

$$ \mathrm{C}_{n}^{k}=\dfrac{n!}{k!(n-k)!}=\mathrm{C}_{n}^{n-k} $$

注意这不是“把一个数拆成两份”,而是用两个视角描述同一种选择。

应用辨析:把复杂下标换成简单下标

例如 $\mathrm{C}_{12}^{10}=\mathrm{C}_{12}^{2}=66$,选择“排除谁”往往更方便。

注意

互补的是同一个总体 $n$ 中的 $k$ 与 $n-k$,不能随意更换总人数。

课堂小测

课堂小测

$\mathrm{C}_{10}^{8}$ 等于哪一个组合数?

查看答案与解析

答案A

解析

$8$ 与 $2$ 是相对于同一总体 $10$ 的互补下标。

辨析
  • B:总体人数必须仍然是 $10$
  • C:互补下标应为 $10-8=2$
  • D:对称性不改变总体人数。
专题 04

帕斯卡递推

选不选某个指定元素?一个问题分成互不重叠的两类。

核心公式

$$\mathrm{C}_{n}^{k}=\mathrm{C}_{n-1}^{k-1}+\mathrm{C}_{n-1}^{k}$$

条件:$n\ge 1$,$0\le k\le n$;下标越界的组合数按 $0$ 计算。

杨辉三角前 8 行(第 0 至第 7 行)。绿色格 \mathrm{C}_{6}^{2}=15 对应“选指定元素”,黄色格 \mathrm{C}_{6}^{3}=20 对应“不选指定元素”,两个箭头汇入紫色格 \mathrm{C}_{7}^{3}=35(全部选法),即 \mathrm{C}_{7}^{3}=\mathrm{C}_{6}^{2}+\mathrm{C}_{6}^{3}=15+20=35。
图 1杨辉三角前 8 行(第 0 至第 7 行)。绿色格 $\mathrm{C}_{6}^{2}=15$ 对应“选指定元素”,黄色格 $\mathrm{C}_{6}^{3}=20$ 对应“不选指定元素”,两个箭头汇入紫色格 $\mathrm{C}_{7}^{3}=35$(全部选法),即 $\mathrm{C}_{7}^{3}=\mathrm{C}_{6}^{2}+\mathrm{C}_{6}^{3}=15+20=35$。

把公式拆开看

以 $n=7$,$k=3$ 为例,公式右边的两项各有一个确切的含义,并对应三角形中上一行的一个格子:

算式 数值 含义
选指定元素:$\mathrm{C}_{6}^{2}$ $15$ 已选定 $1$ 人,再从 $6$ 人中选 $2$ 人
不选指定元素:$\mathrm{C}_{6}^{3}$ $20$ 从剩下的 $6$ 人中选 $3$ 人

$$\mathrm{C}_{7}^{3}=\mathrm{C}_{6}^{2}+\mathrm{C}_{6}^{3}=15+20=35$$

一般地,若 $k=0$,则“选指定元素”这一类不可能出现,计数为 $0$;若 $k=n$(需要选出全部 $n$ 人),则“不选指定元素”这一类不可能出现,计数为 $0$。

观察规律:两个父格,汇入一个结果

两个上方格的数是 $15$ 与 $20$,相加得到 $35$。边界外不存在的格子按 $0$ 处理。

计数解释:对一个指定元素分类

指定元素甲。所有 $k$ 元子集分为“包含甲”和“不包含甲”两类;每个子集恰好属于其中一类。

  • 包含甲:还要选 $k-1$ 个;
  • 不含甲:仍要选 $k$ 个;

两类中,可供选择的元素都只剩 $n-1$ 个。

推导证明:用分类加法得到递推

$$\mathrm{C}_{n}^{k}=\mathrm{C}_{n-1}^{k-1}+\mathrm{C}_{n-1}^{k}$$

从顶部的 $1$ 与两侧的 $1$ 出发,这条规则生成整个杨辉三角。

应用辨析:正向拆分,反向合并

例如 $\mathrm{C}_{8}^{3}+\mathrm{C}_{8}^{4}=\mathrm{C}_{9}^{4}$。相加的两项总人数相同、下标相邻。

注意

合并后总人数加 $1$,下标取两项中较大的一个;不能只看“两个组合数相加”就套递推。

相关专题:朱世杰恒等式;部分交错和。

课堂小测

课堂小测

$\mathrm{C}_{8}^{3}+\mathrm{C}_{8}^{4}$ 等于什么?

查看答案与解析

答案A

解析

总人数由 $8$ 增到 $9$,下标取 $4$。

辨析
  • B:下标不相加,应取较大的 $4$
  • C:总体要加 $1$,下标不相加
  • D:合并后的下标取较大的 $4$。
专题 05

相邻组合数的比值

把增长与下降写成一个分式,找到每一行的转折。

核心公式

$$ \dfrac{\mathrm{C}_{n}^{k}}{\mathrm{C}_{n}^{k-1}} = \dfrac{n-k+1}{k} $$

条件:$n\ge 1$,$1\le k\le n$。$k=0$ 时分母为 $0$,比值没有定义。

杨辉三角前 9 行(第 0–8 行)。第 8 行中浅绿色格为 \mathrm{C}_8^2=28(比值的分母项),黄色格为 \mathrm{C}_8^3=56(分子项);示例参数 n=8,\ k=3 下 \dfrac{\mathrm{C}_{8}^{3}}{\mathrm{C}_{8}^{2}} = \dfrac{56}{28} = \dfrac{6}{3} = 2。
图 1杨辉三角前 9 行(第 0–8 行)。第 8 行中浅绿色格为 $\mathrm{C}_8^2=28$(比值的分母项),黄色格为 $\mathrm{C}_8^3=56$(分子项);示例参数 $n=8,\ k=3$ 下 $\dfrac{\mathrm{C}_{8}^{3}}{\mathrm{C}_{8}^{2}} = \dfrac{56}{28} = \dfrac{6}{3} = 2$。

观察相邻两项的增减

第 8 行组合数的柱状图:深绿色最高柱为 \mathrm{C}_8^4=70,浅绿与橙色的 k=2,3 两柱满足 56/28=2。各柱先增后减,且关于 k=4 对称。
图 2第 $8$ 行组合数的柱状图:深绿色最高柱为 $\mathrm{C}_8^4=70$,浅绿与橙色的 $k=2,3$ 两柱满足 $56/28=2$。各柱先增后减,且关于 $k=4$ 对称。

用具体对象理解计数:以第 8 行为例,用柱高表示该行的组合数 $\mathrm{C}_8^k$($k=0,1,\dots,8$),横轴为下标 $k$。该行的最大值为 $\mathbf{70}$(深绿色柱),中间只有一个最高柱;两侧相邻的组合数先逐项增大、后逐项减小,可与上图第 8 行逐格对照。

观察规律:用比值判断大小

取 $n=8,\ k=3$,比值为 $\dfrac{6}{3}=2>1$,因此后一项 $\mathrm{C}_8^3$ 大于前一项 $\mathrm{C}_8^2$。

一般地,比值大于 $1$ 时后一项大于前一项,等于 $1$ 时两项相等,小于 $1$ 时后一项小于前一项。

计数解释:给小组添加一位新成员

先选 $k-1$ 人,再从组外选 $1$ 人,有 $\mathrm{C}_n^{k-1}(n-k+1)$ 种;先选 $k$ 人,再标记其中最后加入的 $1$ 人,有 $\mathrm{C}_n^{k}\,k$ 种。

推导证明:阶乘相除,只剩一个比值

$$ \dfrac{\mathrm{C}_{n}^{k}}{\mathrm{C}_{n}^{k-1}}=\dfrac{(k-1)!\,(n-k+1)!}{k!\,(n-k)!}=\dfrac{n-k+1}{k} $$

比值 $\ge 1\iff k\le\dfrac{n+1}{2}$;等号出现在 $k=\dfrac{n+1}{2}$ 为整数时。

应用辨析:定位峰值与比较大小

不必算出巨大的组合数,只要判断比值与 $1$ 的关系,就能比较相邻项。

注意

这里比较的是组合数。对于 $\mathrm{C}_n^k a^{n-k}b^k$,幂因子也影响大小。

相关专题:最大二项式系数;吸收恒等式。

课堂小测

课堂小测

第 9 行中,$\dfrac{\mathrm{C}_9^5}{\mathrm{C}_9^4}$ 等于多少?

查看答案与解析

答案A

解析

$\dfrac{9-5+1}{5}=1$,因此第 9 行有两个相等的中间最大数。

辨析
  • B:代入的是 $k=5$,分母为 $5$
  • C:分子 $n-k+1=5$,不是 $4$
  • D:相邻比值应使用 $\dfrac{n-k+1}{k}$。
专题 06

最大二项式系数

中间为什么最大?奇数行与偶数行又有什么不同?

核心公式

$$ \max_{0\le k\le n}\mathrm{C}_n^k =\mathrm{C}_n^{\lfloor n/2\rfloor} =\mathrm{C}_n^{\lceil n/2\rceil} $$

$n,k$ 为整数,$0\le k\le n$。

第 9 行的浅绿色格表示左侧递增部分,黄色格表示右侧递减部分,紫色两格为中间的最大值:\mathrm{C}_9^4=\mathrm{C}_9^5=126。上下各行均从下标 0 开始。
图 1第 9 行的浅绿色格表示左侧递增部分,黄色格表示右侧递减部分,紫色两格为中间的最大值:$\mathrm{C}_9^4=\mathrm{C}_9^5=126$。上下各行均从下标 $0$ 开始。

整行的形状:先增后减

用具体对象理解计数:横轴为下标 $k$,柱高表示 $\mathrm{C}_n^k$。偶数行有单个峰值,奇数行有两个等高峰值。

以 $n=9$ 为例,各下标及组合数如下;最大值为 $126$,中间两柱一样高。

$k$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$
$\mathrm{C}_9^k$ $1$ $9$ $36$ $84$ $126$ $126$ $84$ $36$ $9$ $1$

观察规律:峰值出现在哪里

$n=9$ 为奇数,最大值位于下标 $4$ 与 $5$,值为 $126$。

计数解释:从相邻比值理解结构

逐个扩大入选人数,组合数先增大,再减小。对称性把两边配对,而比值公式严格确定转折点。

推导证明:解一个简单不等式

$$ \frac{\mathrm{C}_n^k}{\mathrm{C}_n^{k-1}} =\frac{n-k+1}{k}\ge1 \iff k\le\frac{n+1}{2} $$

$n$ 为偶数时,中间一个最大;$n$ 为奇数时,中间两个相等且最大。

应用辨析:二项式系数最大 ≠ 任意展开式系数最大

对 $(a+b)^n$,二项式系数是 $\mathrm{C}_n^k$。对 $(1+2x)^n$,$x^k$ 的系数是 $2^k\mathrm{C}_n^k$,峰值位置可能移动。

注意

判断“最大项”前,先确认比较对象是二项式系数、展开式系数,还是代入后的项值。

相关专题:相邻组合数的比值;二项式定理与通项。

课堂小测

课堂小测

第 11 行的最大组合数出现在什么下标?

查看答案与解析

答案A

解析

奇数行有两个相等的中间最大组合数。

辨析
  • B:$k=6$ 与 $k=5$ 对称且相等
  • C:$k=5$ 与 $k=6$ 对称且相等
  • D:边界组合数等于 $1$,并非本行最大值。
专题 07

行和与所有子集

每个元素都有“选”和“不选”两种决定。

核心公式

$$ \sum_{i=0}^n\mathrm{C}_n^i=2^n $$

$n,k$ 为整数,$0\le k\le n$。

第 6 行全部浅绿色格对应所有可能的子集大小;各格组合数相加为 1+6+15+20+15+6+1=2^6=64。橙色外框强调下标 0 的空集项。
图 1第 6 行全部浅绿色格对应所有可能的子集大小;各格组合数相加为 $1+6+15+20+15+6+1=2^6=64$。橙色外框强调下标 $0$ 的空集项。

把公式拆开看

按子集大小分类,每类的计数为 $\mathrm{C}_6^i$;各类合在一起覆盖所有子集。

选取个数 $i$ $0$ $1$ $2$ $3$ $4$ $5$ $6$
计数 $\mathrm{C}_6^i$ $1$ $6$ $15$ $20$ $15$ $6$ $1$

例如,$\mathrm{C}_6^0=1$,即大小为 $0$ 的子集有 $1$ 个。

观察规律:把一整行加起来

第 6 行有 $7$ 个数,和为 $64$。$n$ 增加 $1$ 时,行和翻倍。

计数解释:每个元素都有两种状态

$n$ 个元素各自决定“选”或“不选”,分步乘法给出 $2^n$ 种子集;也可以按子集的大小 $i$ 分类,得到左边的和。

推导证明:从二项式定理赋值

$$ (1+1)^n=\sum_{i=0}^n\mathrm{C}_n^i1^{n-i}1^i=2^n $$

$n=0$ 时只有空集一个子集,行和仍是 $1$。

应用辨析:注意有没有漏掉空集

所有子集数为 $2^n$;非空子集数为 $2^n-1$;$n\ge1$ 时非空真子集数为 $2^n-2$。

注意

“至少选一个”需要扣除 $\mathrm{C}_n^0=1$。

相关专题:二项式定理与通项;一次带权求和;奇偶下标和。

课堂小测

课堂小测

6 个元素的非空子集有多少个?

查看答案与解析

答案A

解析

$2^6-1=63$,扣除空集即可。

辨析
  • B:$64$ 包含空集
  • C:$32$ 是偶数大小或奇数大小子集的数量
  • D:$62$ 同时扣除了空集与全集,题目没有排除全集。
专题 08

交错和

把奇数大小与偶数大小的子集一一配对。

核心公式

$$ \sum_{i=0}^n(-1)^i\mathrm{C}_n^i=0 $$

$n\ge1$。$n=0$ 时只有 $\mathrm{C}_0^0=1$,两类和不相等。

第 6 行浅绿色格为偶数下标,黄色格为奇数下标;按正负交替相加得 1-6+15-20+15-6+1=0,两类组合数的总和均为 32。橙色外框强调首项。
图 1第 6 行浅绿色格为偶数下标,黄色格为奇数下标;按正负交替相加得 $1-6+15-20+15-6+1=0$,两类组合数的总和均为 $32$。橙色外框强调首项。

把公式拆开看

下标 $i$ $0$ $1$ $2$ $3$ $4$ $5$ $6$
下标奇偶 偶 奇 偶 奇 偶 奇 偶
带符号的项 $(-1)^i\mathrm{C}_6^i$ $1$ $-6$ $15$ $-20$ $15$ $-6$ $1$

例如,$\mathrm{C}_6^0=1$。下标 $i=0$ 是偶数;它位于从左往右第 $1$ 项,在交错和中取正号。其他项也按下标奇偶分别取正号、负号。

观察规律:按下标奇偶分成两类

偶数下标的和是 $32$,奇数下标的和也是 $32$。正负相减恰好抵消。

计数解释:切换一个固定元素的入选状态

固定一个元素甲。对任何子集,若甲在其中就移除甲,若甲不在其中就加入甲。子集大小的奇偶性改变;再切换一次会回到原子集。

因此奇数大小与偶数大小的子集一一配对,数量相等。

推导证明:两次赋值,联立求解

$$ \begin{aligned} E+O&=2^n,\\ E-O&=(1-1)^n=0, \end{aligned} $$

$$ E=O=2^{n-1} $$

$E$ 表示偶数下标和,$O$ 表示奇数下标和。$n\ge1$ 保证可以选定一个元素,也保证 $(1-1)^n=0$。

应用辨析:项的位置要与下标分开

注意

$\mathrm{C}_n^0$ 是第 $1$ 项:偶数下标对应奇数位置,奇数下标对应偶数位置。这里也不是按组合数的数值奇偶分类。

题目限制“选奇数个人”或“选偶数个人”,可以直接使用这两个半行和。

相关专题:奇偶下标和;部分交错和;二项式定理与通项。

课堂小测

课堂小测

$\mathrm{C}_n^0,\mathrm{C}_n^2,\mathrm{C}_n^4,\dots$ 这一组应该怎样准确称呼?

查看答案与解析

答案A

解析

下标为 $0,2,4$;在整行中却是第 $1,3,5,\dots$ 项。

辨析
  • B:它们位于第 $1,3,5,\dots$ 项,位置是奇数
  • C:下标偶数与组合数的数值奇偶无关
  • D:下标 $0,2,4$ 都是偶数。
专题 09

奇偶下标和

各占一半的是下标奇偶,不是格子数值的奇偶。

核心公式

$$ \begin{aligned} \sum_{\substack{0\le i\le n\\i\text{ 为偶数}}}\mathrm{C}_n^i &=\sum_{\substack{0\le i\le n\\i\text{ 为奇数}}}\mathrm{C}_n^i\\ &=2^{n-1} \end{aligned} $$

$n\ge1$。$n=0$ 时只有 $\mathrm{C}_0^0=1$,两类和不相等。

第 7 行浅绿色格为偶数下标,黄色格为奇数下标;两类之和均为 64=2^6。颜色按下标奇偶区分,与格内数值的奇偶无关;橙色外框强调首项。
图 1第 7 行浅绿色格为偶数下标,黄色格为奇数下标;两类之和均为 $64=2^6$。颜色按下标奇偶区分,与格内数值的奇偶无关;橙色外框强调首项。

把公式拆开看

下标 $i$ $0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$
下标奇偶 偶 奇 偶 奇 偶 奇 偶 奇
$\mathrm{C}_7^i$ $1$ $7$ $21$ $35$ $35$ $21$ $7$ $1$

例如,$\mathrm{C}_7^0=1$。下标 $i=0$ 是偶数,位于从左往右第 $1$ 项;同色项累加得到 $2^{n-1}$。

观察规律:按下标奇偶分成两类

偶数下标的和是 $64$,奇数下标的和也是 $64$。各为整行总和的一半。

计数解释:切换一个固定元素的入选状态

固定一个元素甲。对任何子集,若甲在其中就移除甲,若甲不在其中就加入甲。子集大小的奇偶性改变;再切换一次会回到原子集。

因此奇数大小与偶数大小的子集一一配对,数量相等。

推导证明:两次赋值,联立求解

$$ \begin{aligned} E+O&=2^n,\\ E-O&=(1-1)^n=0, \end{aligned} $$

$$ E=O=2^{n-1} $$

$E$ 表示偶数下标和,$O$ 表示奇数下标和。$n\ge1$ 保证可以选定一个元素,也保证 $(1-1)^n=0$。

应用辨析:项的位置要与下标分开

注意

$\mathrm{C}_n^0$ 是第 $1$ 项:偶数下标对应奇数位置,奇数下标对应偶数位置。这里也不是按组合数的数值奇偶分类。

题目限制“选奇数个人”或“选偶数个人”,可以直接使用这两个半行和。

相关专题:交错和;行和与所有子集。

课堂小测

课堂小测

$\mathrm{C}_n^0,\mathrm{C}_n^2,\mathrm{C}_n^4,\dots$ 这一组应该怎样准确称呼?

查看答案与解析

答案A

解析

下标为 $0,2,4$;在整行中却是第 $1,3,5,\dots$ 项。

辨析
  • B:它们位于第 $1,3,5,\dots$ 项,位置是奇数
  • C:下标偶数与组合数的数值奇偶无关
  • D:下标 $0,2,4$ 都是偶数。
专题 10

朱世杰恒等式

沿一条斜线累加,为什么会落在末端的“折角”?

核心公式

$$ \sum_{i=k}^n\mathrm{C}_i^k=\mathrm{C}_{n+1}^{k+1} $$

$n,k$ 为整数,$0\le k\le n$。

浅绿色格沿固定下标 2 的斜线排列,箭头依次连接这些求和项,再折向下一行紫色结果格:1+3+6+10+15+21=\mathrm{C}_8^3=56。
图 1浅绿色格沿固定下标 $2$ 的斜线排列,箭头依次连接这些求和项,再折向下一行紫色结果格:$1+3+6+10+15+21=\mathrm{C}_8^3=56$。

把公式拆开看

从 $1$ 到 $8$ 选 $3$ 个数,按最大元素分类。

最大元素 $3$ $4$ $5$ $6$ $7$ $8$
计数 $\mathrm{C}_2^2$ $\mathrm{C}_3^2$ $\mathrm{C}_4^2$ $\mathrm{C}_5^2$ $\mathrm{C}_6^2$ $\mathrm{C}_7^2$
数值 $1$ $3$ $6$ $10$ $15$ $21$

例如,最大元素为 $3$ 时,其余 $2$ 个只能从前 $2$ 个数中选,故 $\mathrm{C}_2^2=1$。其余各类中,固定最大元素后,同样从它前面的数中选出剩余 $2$ 个。

观察规律:沿固定下标的斜线走

从 $\mathrm{C}_2^2$ 开始,沿下标 $2$ 的斜线一直加到 $\mathrm{C}_7^2$,总和落在下一行右下方的 $\mathrm{C}_8^3$。

计数解释:按所选元素的最大值分类

从 $\{1,2,\dots,n+1\}$ 中选 $k+1$ 个数。若最大数是 $i+1$,就从前 $i$ 个数里再选 $k$ 个,计数为 $\mathrm{C}_i^k$。

最大数依次取 $k+1,\dots,n+1$;各类互斥且覆盖所有选法。

推导证明:递推也能逐项消去

$$ \mathrm{C}_i^k=\mathrm{C}_{i+1}^{k+1}-\mathrm{C}_i^{k+1} $$

令 $i$ 从 $k$ 到 $n$ 求和,中间相邻项全部抵消。只剩 $\mathrm{C}_{n+1}^{k+1}-\mathrm{C}_k^{k+1}$,最后一项为 $0$。

应用辨析:识别求和方向

例如:

$$ 1+2+\cdots+n=\mathrm{C}_{n+1}^2 $$

$$ 1+3+6+\cdots+\mathrm{C}_n^2=\mathrm{C}_{n+1}^3 $$

注意

该公式固定选取个数 $k$,让总体 $i$ 变化;与固定总体 $n$ 的行和不是同一种求和。

相关专题:帕斯卡递推;双重选取恒等式。

课堂小测

课堂小测

$\mathrm{C}_2^2+\mathrm{C}_3^2+\mathrm{C}_4^2+\mathrm{C}_5^2$ 等于什么?

查看答案与解析

答案A

解析

最后一项总人数 $5$ 加 $1$,下标 $2$ 加 $1$。

辨析
  • B:结果应在末项的下一行,即第 $6$ 行
  • C:下标也要加 $1$
  • D:末项是第 $5$ 行,结果应是第 $6$ 行。
专题 11

部分交错和

没有加完整行时,正负相消还会留下什么?

核心公式

$$ \sum_{i=0}^k(-1)^i\mathrm{C}_n^i=(-1)^k\mathrm{C}_{n-1}^k $$

$n\ge1$,$0\le k\le n$;$k=n$ 时右侧组合数越界为 $0$,退化为整行交错和。

第 7 行只取下标 0 至 3:浅绿色格为正号项,黄色格为负号项;上一行紫色格为抵消后组合数的绝对值 \mathrm{C}_6^3=20。末下标为奇数,故 1-7+21-35=-\mathrm{C}_6^3=-20。
图 1第 7 行只取下标 $0$ 至 $3$:浅绿色格为正号项,黄色格为负号项;上一行紫色格为抵消后组合数的绝对值 $\mathrm{C}_6^3=20$。末下标为奇数,故 $1-7+21-35=-\mathrm{C}_6^3=-20$。

把公式拆开看

下标 $i$ $0$ $1$ $2$ $3$
带符号的项 $(-1)^i\mathrm{C}_7^i$ $1$ $-7$ $21$ $-35$
累计部分和 $1$ $-6$ $15$ $-20$

例如,$\mathrm{C}_7^0=1$,累计到 $i=0$ 时,部分和为 $1$;一般累计到下标 $i$ 时,部分和为 $(-1)^i\mathrm{C}_6^i$。

观察规律:截断后不一定为零

只加到下标 $3$,部分交错和为 $-20$。截断下标 $k$ 改变时,部分和的符号正负交替,其绝对值与上一行的组合数相联系。

计数解释:配对时,哪些子集留了下来

固定元素甲,把“不含甲的 $S$”与“含甲的 $S\cup\{\text{甲}\}$”配对。若 $|S|\le k-1$,两者都在截断范围内,符号相反而抵消。

唯独不含甲、大小恰好为 $k$ 的子集,其配对大小为 $k+1$,超出范围。留下 $\mathrm{C}_{n-1}^k$ 个,符号为 $(-1)^k$。

推导证明:递推拆项,相邻抵消

$$ \mathrm{C}_n^i=\mathrm{C}_{n-1}^i+\mathrm{C}_{n-1}^{i-1} $$

乘 $(-1)^i$ 并从 $i=0$ 累加到 $k$。第二部分把下标换成 $j=i-1$,符号改变,恰好抵消第一部分的前 $k$ 项。

剩余:

$$ (-1)^k\mathrm{C}_{n-1}^k $$

应用辨析:检查是否真的加到整行末尾

注意

只有 $k=n$ 时,这个截断和才必为 $0$。不能把整行交错和公式套在任意部分和上。

适用于组合数正负交替、但求和终点不是 $n$ 的题目。

相关专题:帕斯卡递推;交错和。

课堂小测

课堂小测

$1-\mathrm{C}_6^1+\mathrm{C}_6^2-\mathrm{C}_6^3$ 的值是多少?

查看答案与解析

答案A

解析

$(-1)^3\mathrm{C}_5^3=-10$。

辨析
  • B:这是截断到 $k=3$ 的部分和,没有加完整行
  • C:末下标 $k=3$ 为奇数,结果取负号
  • D:结果组合数在上一行,为 $\mathrm{C}_5^3$。
专题 12

吸收恒等式

先选队伍再选队长,或先选队长再组队。

核心公式

$$ k\mathrm{C}_n^k=n\mathrm{C}_{n-1}^{k-1} $$

$n\ge1$,$1\le k\le n$。这里用“选队长”的情境,要求队伍非空。

同一批带队长的 3 人队伍,两条计数路径:绿色先选队伍再选队长,橙色先选队长再补队员;两条路径都得到紫色框中的 105 种。
图 1同一批带队长的 $3$ 人队伍,两条计数路径:绿色先选队伍再选队长,橙色先选队长再补队员;两条路径都得到紫色框中的 $105$ 种。

把公式拆开看

计数顺序 算式 结果
先队伍,后队长 $\mathrm{C}_7^3\times3$ $105$
先队长,后队员 $7\times\mathrm{C}_6^2$ $105$

先选队伍时,有 $35$ 个队伍,每个队伍有 $3$ 位可能的队长,故 $\mathrm{C}_7^3\times3=105$。

先选队长时,有 $7$ 位可能的队长;固定队长后,在剩下 $6$ 人中选 $2$ 名队员,故 $7\times\mathrm{C}_6^2=105$。

观察规律:系数 $k$ 与 $n$ 从何而来

两边同为 $105$,但乘数 $3$ 与 $7$ 表示在不同阶段选择队长。

计数解释:数同一种带标记的队伍

对象是“一个 $k$ 人队伍,以及其中的一名队长”。路径一先组队再任命;路径二先任命再补齐队伍。

思路

双重计数的关键:两条路径必须得到完全相同的一批对象。

推导证明:阶乘中的 $k$ 被吸收

$$ k\mathrm{C}_n^k =\frac{n!}{(k-1)!(n-k)!} =n\mathrm{C}_{n-1}^{k-1} $$

把外面的 $k$ 吸收到组合数中,同时让总体和选取数各减 $1$。

应用辨析:带权求和的入口

遇到 $\sum_{k=0}^n k\mathrm{C}_n^k$,先吸收,再把剩下的组合数求和,得到 $n2^{n-1}$。

注意

降阶后求和下标与上下限要一起调整;不能只改组合数、不改求和范围。

相关专题:一次带权求和;双重选取恒等式。

课堂小测

课堂小测

$k\mathrm{C}_n^k$ 应如何改写?

查看答案与解析

答案A

解析

总体与选取数各降 $1$,外部因子变成 $n$。

辨析
  • B:先指定队长后,剩下还要选 $k-1$ 人
  • C:先选队长有 $n$ 种选择
  • D:吸收必须同时调整总体、选取数与外部因子。
专题 13

双重选取恒等式

一支队伍中的核心小组,可以用两种顺序选出。

核心公式

$$ \mathrm{C}_n^k\mathrm{C}_k^r =\mathrm{C}_n^r\mathrm{C}_{n-r}^{k-r} $$

$0\le r\le k\le n$,均为整数。

浅绿色两格为先选大组、再选核心组的两个因子 \mathrm{C}_8^5 与 \mathrm{C}_5^2;黄色两格为先选核心组、再补队员的两个因子 \mathrm{C}_8^2 与 \mathrm{C}_6^3。两种路径都计数嵌套小组,总数为 56\times10=28\times20=560。
图 1浅绿色两格为先选大组、再选核心组的两个因子 $\mathrm{C}_8^5$ 与 $\mathrm{C}_5^2$;黄色两格为先选核心组、再补队员的两个因子 $\mathrm{C}_8^2$ 与 $\mathrm{C}_6^3$。两种路径都计数嵌套小组,总数为 $56\times10=28\times20=560$。

把公式拆开看

计数顺序 算式 结果
先选大组 $\mathrm{C}_8^5\times\mathrm{C}_5^2$ $560$
先选核心组 $\mathrm{C}_8^2\times\mathrm{C}_6^3$ $560$

先选 $5$ 人队伍,再从队内选 $2$ 人核心小组,得 $\mathrm{C}_8^5\times\mathrm{C}_5^2=560$。

也可以先选 $2$ 人核心小组,再从剩余 $6$ 人中补 $3$ 人,得 $\mathrm{C}_8^2\times\mathrm{C}_6^3=560$。

观察规律:两级选取,交换顺序

这里计数的是“$5$ 人队伍 + 其中 $2$ 人核心组”。两条路径都得到 $560$。

计数解释:固定最终对象再拆步骤

每个结果是一对集合 $(R,K)$,满足 $R\subseteq K\subseteq\text{总体}$,$|R|=r$,$|K|=k$。先确定 $K$ 或先确定 $R$,都唯一确定后续选择的范围。

推导证明:约分为同一个阶乘式

$$ \begin{aligned} \mathrm{C}_n^k\mathrm{C}_k^r &=\frac{n!}{r!(k-r)!(n-k)!}\\ &=\mathrm{C}_n^r\mathrm{C}_{n-r}^{k-r} \end{aligned} $$

取 $r=1$,就得到 $k\mathrm{C}_n^k=n\mathrm{C}_{n-1}^{k-1}$,即吸收恒等式。

应用辨析:把“内层选取”转移到外层

含 $\mathrm{C}_n^k\mathrm{C}_k^r$ 的乘积常能借此重排。对 $k$ 从 $r$ 到 $n$ 求和,还能得到组合权重求和:

$$ \sum_{k=r}^n\mathrm{C}_n^k\mathrm{C}_k^r =\mathrm{C}_n^r2^{n-r} $$

注意

核心小组内不区分职务;若 $r$ 人担任不同职务,还需要额外乘 $r!$。

相关专题:吸收恒等式;降阶阶乘带权和。

课堂小测

课堂小测

$\mathrm{C}_8^5\mathrm{C}_5^2$ 等于哪一个乘积?

查看答案与解析

答案A

解析

先选 $2$ 名核心成员,再从剩余 $6$ 人中补 $3$ 人。

辨析
  • B:选出核心组后,补人总体只剩 $6$ 人,不能重复选核心成员
  • C:重排时先选核心组,大小为 $2$
  • D:最终对象必须是核心组包含于大组的嵌套关系。
专题 14

一次带权求和

$k$ 不只是一个系数:它表示队伍里队长的选择数。

核心公式

$$\sum_{i=0}^{n}i\mathrm{C}_{n}^{i} = n2^{n-1}$$

$n\ge1$,求和包含 $i=0$ 项,但该项权重为 $0$。

第 7 行的绿底格表示按队伍大小分类所用的组合数,第 6 行的橙底格表示先选队长后其余成员的选择数;吸收恒等式把带权求和化为上一行的行和。橙色描边标出示例 i=0,深绿描边标出选中的 \mathrm{C}_7^3。
图 1第 $7$ 行的绿底格表示按队伍大小分类所用的组合数,第 $6$ 行的橙底格表示先选队长后其余成员的选择数;吸收恒等式把带权求和化为上一行的行和。橙色描边标出示例 $i=0$,深绿描边标出选中的 $\mathrm{C}_7^3$。

以 $n=7$ 为例:

$$ \begin{aligned}0+7+42+105+140+105\\&\quad+42+7=448 \end{aligned} $$

权重 × 该大小的队伍数

小于所需职务数的队伍贡献为 $0$。

队伍人数 $i$ 权重 队伍数 贡献
$0$ $0$ $\mathrm{C}_7^0=1$ $0$
$1$ $1$ $\mathrm{C}_7^1=7$ $7$
$2$ $2$ $\mathrm{C}_7^2=21$ $42$
$3$ $3$ $\mathrm{C}_7^3=35$ $105$
$4$ $4$ $\mathrm{C}_7^4=35$ $140$
$5$ $5$ $\mathrm{C}_7^5=21$ $105$
$6$ $6$ $\mathrm{C}_7^6=7$ $42$
$7$ $7$ $\mathrm{C}_7^7=1$ $7$

$$0 \times \mathrm{C}_{7}^{0} = 0$$

以 $i=0$ 为例,队伍无人,无法安排一名队长,因此贡献为 $0$。

$i\ge1$ 时,上表每项也可写成 $7\mathrm{C}_6^{i-1}$。

观察规律:把整行的每个数乘以下标

把 $\mathrm{C}_7^i$ 乘 $i$ 再求和,得到 $448$。这里下标权重不能直接提出求和号。

计数解释:队伍大小不限,但需要一名队长

按队伍大小 $i$ 分类,每类有 $i\mathrm{C}_n^i$ 种。换个顺序:先从 $n$ 人里选队长,再让剩下 $n-1$ 人各自决定加入或不加入。

推导证明:吸收,再平移求和下标

$$\sum_{i=1}^{n}i\mathrm{C}_{n}^{i}=n\sum_{i=1}^{n}\mathrm{C}_{n-1}^{i-1}=n2^{n-1}$$

令 $j=i-1$,则 $j$ 从 $0$ 到 $n-1$,恰好成为上一行的行和。

应用辨析:从权重识别标记对象

$i$ 表示在 $i$ 人队伍里标记一人;类似地,$i(i-1)$ 表示标记两名不同职务的人。

注意

不能把可变的 $i$ 当作常数移到求和号外。

课堂小测

课堂小测

$\sum_{i=0}^6 i\mathrm{C}_6^i$ 等于多少?

查看答案与解析

答案A

解析

$6\times2^5=192$。

辨析
  • B:选定队长后,只有剩余 5 人能自由决定入选
  • C:64 是所有队伍数,未统计队长
  • D:使用 $n2^{n-1}$,指数是 $5$。

相关专题:吸收恒等式、降阶阶乘带权和、平方权重求和。

专题 15

降阶阶乘带权和

把一个职务推广到 $r$ 个不同职务,统一一族求和公式。

核心公式

$$\sum_{i=r}^{n}i^{\underline{r}}\mathrm{C}_{n}^{i} = n^{\underline{r}}2^{n-r}$$

$0\le r\le n$。降阶阶乘 $i^{\underline{r}}=i(i-1)\cdots(i-r+1)$ 是 $i$ 的 $r$ 阶下降积;$r=0$ 时空乘积为 $1$。

第 7 行的绿底格与第 5 行的橙底格,分别对应先组队和先安排两个不同职务后的自由选取。安排职务后总体和选取人数均降两阶;人数不足时贡献为 0。
图 1第 $7$ 行的绿底格与第 $5$ 行的橙底格,分别对应先组队和先安排两个不同职务后的自由选取。安排职务后总体和选取人数均降两阶;人数不足时贡献为 $0$。

以 $n=7$ 为例:

$$ \begin{aligned}0+0+42+210+420+420\\&\quad+210+42=1344 \end{aligned} $$

权重 × 该大小的队伍数

小于所需职务数的队伍贡献为 $0$。

队伍人数 $i$ 权重 队伍数 贡献
$0$ $0(0-1)=0$ $\mathrm{C}_7^0=1$ $0$
$1$ $1(1-1)=0$ $\mathrm{C}_7^1=7$ $0$
$2$ $2(2-1)=2$ $\mathrm{C}_7^2=21$ $42$
$3$ $3(3-1)=6$ $\mathrm{C}_7^3=35$ $210$
$4$ $4(4-1)=12$ $\mathrm{C}_7^4=35$ $420$
$5$ $5(5-1)=20$ $\mathrm{C}_7^5=21$ $420$
$6$ $6(6-1)=30$ $\mathrm{C}_7^6=7$ $210$
$7$ $7(7-1)=42$ $\mathrm{C}_7^7=1$ $42$

$$0^{\underline{2}} \times \mathrm{C}_{7}^{0} = 0$$

以 $i=0$ 为例,队伍无人,无法安排两个不同职务,因此贡献为 $0$。

$i\ge2$ 时,上表每项也可写成 $42\mathrm{C}_5^{i-2}$。

观察规律:高阶权重也能统一处理

取 $r=2$,权重为 $i(i-1)$。把这些权重乘入第 $7$ 行并求和,得到 $1344$。

计数解释:先选带 $r$ 个不同职务的队伍

队伍大小为 $i$ 时,先选成员,再给 $r$ 个不同职务安排不同的人,有 $i^{\underline{r}}\mathrm{C}_n^i$ 种。

也可以先从 $n$ 人中有序确定 $r$ 位任职者,共 $n^{\underline{r}}$ 种,再让其余 $n-r$ 人自由加入或不加入。

推导证明:反复吸收,一次降 $r$ 阶

$$i^{\underline{r}}\mathrm{C}_{n}^{i}=n^{\underline{r}}\mathrm{C}_{n-r}^{i-r}$$

$$\sum_{i=r}^{n}i^{\underline{r}}\mathrm{C}_{n}^{i}=n^{\underline{r}}2^{n-r}$$

$r=0$ 是行和,$r=1$ 是一次带权和,$r=2$ 是 $i(i-1)$ 带权和。

应用辨析:与普通幂权重的桥梁

$$i^2=i(i-1)+i$$

$$i^3=i(i-1)(i-2)+3i(i-1)+i$$

将普通幂写成降阶阶乘的线性组合,就能处理更高次的带权求和。

注意

降阶阶乘 $i^{\underline{r}}$ 不是普通幂 $i^r$;$r$ 个不同职务不允许兼任。

课堂小测

课堂小测

$\sum_{i=0}^6 i(i-1)\mathrm{C}_6^i$ 等于多少?

查看答案与解析

答案A

解析

$6\times5\times2^4=480$。

辨析
  • B:指定两名任职者后,只剩 4 人自由选择
  • C:192 是一次带权和
  • D:权重 $i(i-1)$ 对应两名不同任职者,不是选满整个队伍。

相关专题:一次带权求和、平方权重求和、双重选取恒等式。

专题 16

平方权重求和

用 $k^2=k(k-1)+k$,拆开一个看似难处理的权重。

核心公式

$$\sum_{i=0}^{n}i^{2}\mathrm{C}_{n}^{i} = n(n+1)2^{n-2}$$

$n\ge1$,求和包含 $i=0$ 项,但该项权重为 $0$。

第 7 行绿底格对应平方权重的原组合数,第 5、6 行橙底格分别对应不兼任与兼任两类。将 i^2 拆成 i(i-1)+i,便可分别降两阶和一阶求和。
图 1第 $7$ 行绿底格对应平方权重的原组合数,第 $5$、$6$ 行橙底格分别对应不兼任与兼任两类。将 $i^2$ 拆成 $i(i-1)+i$,便可分别降两阶和一阶求和。

以 $n=7$ 为例:

$$ \begin{aligned}0+7+84+315+560+525\\&\quad+252+49=1792 \end{aligned} $$

权重 × 该大小的队伍数

小于所需职务数的队伍贡献为 $0$。

队伍人数 $i$ 权重 队伍数 贡献
$0$ $0^2=0$ $\mathrm{C}_7^0=1$ $0$
$1$ $1^2=1$ $\mathrm{C}_7^1=7$ $7$
$2$ $2^2=4$ $\mathrm{C}_7^2=21$ $84$
$3$ $3^2=9$ $\mathrm{C}_7^3=35$ $315$
$4$ $4^2=16$ $\mathrm{C}_7^4=35$ $560$
$5$ $5^2=25$ $\mathrm{C}_7^5=21$ $525$
$6$ $6^2=36$ $\mathrm{C}_7^6=7$ $252$
$7$ $7^2=49$ $\mathrm{C}_7^7=1$ $49$

$$0^2 \times \mathrm{C}_{7}^{0} = 0$$

队伍内有序指定两个职务,允许同一人兼任;以空队伍为例,$0^2=0+0$,两项分别表示不同人担任与同一人兼任的贡献。

观察规律:平方权重与组合数平方不同

本节求和项是 $i^2\mathrm{C}_n^i$,不是 $(\mathrm{C}_n^i)^2$。取 $n=7$ 时总和为 $1792$。

计数解释:两个职务,可以由同一人兼任

从一个 $i$ 人队伍中有序任命两个职务,各有 $i$ 种选择,共 $i^2$ 种。分成“不兼任”和“兼任”两类,分别为 $i(i-1)$ 与 $i$。

推导证明:拆权重,分别调用降阶公式

$$\sum_{i=0}^{n}i^2\mathrm{C}_{n}^{i}=n(n-1)2^{n-2}+n2^{n-1}$$

$$=n(n+1)2^{n-2}$$

上述降两阶推导用于 $n\ge2$;$n=1$ 直接计算为 $1$,与最终公式一致。

应用辨析:继续推广到三次权重

$$\sum_{i=0}^{n}i^3\mathrm{C}_{n}^{i}=n^2(n+3)2^{n-3}\text{(}n\ge 1\text{)}$$

由 $i^3=i^{\underline{3}}+3i^{\underline{2}}+i$ 得到;$n=1,2$ 可直接验证。更高次也沿用同样思路。

注意

不要把 $\sum i^2\mathrm{C}_n^i$ 和 $\sum(\mathrm{C}_n^i)^2$ 混淆:它们计数的对象不同。

课堂小测

课堂小测

处理 $i^2\mathrm{C}_n^i$ 时,哪种拆分能直接使用吸收与降阶?

查看答案与解析

答案A

解析

两部分分别使用二阶与一阶带权和。

辨析
  • B:还缺少 $+i$,对应两职务由同一人兼任
  • C:该等式一般不成立
  • D:展开右边得到 $i^2-2i+2$,一般不等于 $i^2$。

相关专题:一次带权求和、降阶阶乘带权和。

专题 17

范德蒙德恒等式

从两组人中选出一队,按第一组的入选人数分类。

核心公式

$$\sum_{i=0}^{k}\mathrm{C}_{m}^{i}\mathrm{C}_{n}^{k-i} = \mathrm{C}_{m+n}^{k}$$

$m,n$ 为非负整数,$0\le k\le m+n$;越界组合数为 $0$。有效项满足 $\max(0,k-n)\le i\le\min(m,k)$。

绿底格 \mathrm{C}_4^0=1 与橙底格 \mathrm{C}_5^4=5 对应第一组选 0 人、第二组选 4 人;紫底格 \mathrm{C}_9^4=126 是所有可行人数分配的总数。
图 1绿底格 $\mathrm{C}_4^0=1$ 与橙底格 $\mathrm{C}_5^4=5$ 对应第一组选 $0$ 人、第二组选 $4$ 人;紫底格 $\mathrm{C}_9^4=126$ 是所有可行人数分配的总数。

示例参数下:

$$5+40+60+20+1=\mathrm{C}_9^4=126$$

枚举分配:第一组选 $i$ 人,第二组选 $k-i$ 人

第一组选 $i$ 人 第二组选 $4-i$ 人 乘积
$\mathrm{C}_4^0=1$ $\mathrm{C}_5^4=5$ $5$
$\mathrm{C}_4^1=4$ $\mathrm{C}_5^3=10$ $40$
$\mathrm{C}_4^2=6$ $\mathrm{C}_5^2=10$ $60$
$\mathrm{C}_4^3=4$ $\mathrm{C}_5^1=5$ $20$
$\mathrm{C}_4^4=1$ $\mathrm{C}_5^0=1$ $1$

$$\mathrm{C}_{4}^{0} \times \mathrm{C}_{5}^{4} = 5$$

以 $i=0$ 为例,第一组 $4$ 人中选 $0$ 人,第二组 $5$ 人中选 $4$ 人;两步相乘,贡献 $5$。

观察规律:每一项是一种人数分配

总共选 $4$ 人。两组相应的组合数相乘,表示一种人数分配的选法数;把所有可行分配相加,得到 $126$。

计数解释:先分组挑选,或直接合并挑选

两个群体互不重叠。按第一组选了 $i$ 人分类,第二组必须选 $k-i$ 人。每类用乘法,不同类别用加法。

不分组看待这 $m+n$ 个人,直接选 $k$ 人,得到 $\mathrm{C}_{m+n}^k$。

推导证明:从多项式乘法取同次幂系数

$$(1+x)^{m}(1+x)^{n}=(1+x)^{m+n}$$

左边 $x^k$ 的系数来自 $x^i$ 与 $x^{k-i}$ 配对,所以是 $\sum_{i=0}^k\mathrm{C}_m^i\mathrm{C}_n^{k-i}$;右边系数是 $\mathrm{C}_{m+n}^k$。

应用辨析:平方和需要两个条件

注意

仅令 $m=n$,并不能把乘积直接写成平方。还需总选取数 $k=n$,再用 $\mathrm{C}_n^{n-i}=\mathrm{C}_n^i$。

题目出现两组来源、固定总选取数,或组合数乘积卷积时,优先考虑这个恒等式。

课堂小测

课堂小测

范德蒙德中只令 $m=n$,正确的等式是哪一个?

查看答案与解析

答案A

解析

第二个因子的下标仍是 $k-i$,只有再取 $k=n$ 才能借对称性化为平方。

辨析
  • B:仅 $m=n$ 不足以让两个因子相等,还需要 $k=n$
  • C:两组的混合选法不能只用两个组合数相加覆盖
  • D:固定总选取 $k$ 人,需要枚举所有分配。

相关专题:组合数平方和、二项式定理与通项、错位乘积求和。

专题 18

组合数平方和

同一行的平方和,藏在“两组等人数、合选一半”之中。

核心公式

$$\sum_{i=0}^{n}[\mathrm{C}_{n}^{i}]^2 = \mathrm{C}_{2n}^{n}$$

$n$ 为非负整数。平方的是组合数本身,而不是下标。

第 5 行的两因子在 i=0 时重合于左端的 1,分别用绿色与橙色标示;紫底格 \mathrm{C}_{10}^5=252 是第 5 行各组合数的平方和。
图 1第 $5$ 行的两因子在 $i=0$ 时重合于左端的 $1$,分别用绿色与橙色标示;紫底格 $\mathrm{C}_{10}^5=252$ 是第 $5$ 行各组合数的平方和。

示例参数下:

$$1+25+100+100+25+1=\mathrm{C}_{10}^5=252$$

每个平方,都可以还原成一次两组选取

$i$ 第一个因子 第二个因子 乘积
$0$ $\mathrm{C}_5^0$ $\mathrm{C}_5^{0}$ $1$
$1$ $\mathrm{C}_5^1$ $\mathrm{C}_5^{1}$ $25$
$2$ $\mathrm{C}_5^2$ $\mathrm{C}_5^{2}$ $100$
$3$ $\mathrm{C}_5^3$ $\mathrm{C}_5^{3}$ $100$
$4$ $\mathrm{C}_5^4$ $\mathrm{C}_5^{4}$ $25$
$5$ $\mathrm{C}_5^5$ $\mathrm{C}_5^{5}$ $1$

$$\mathrm{C}_{5}^{0} \times \mathrm{C}_{5}^{0} = 1$$

以 $i=0$ 为例,利用对称性 $\mathrm{C}_5^0=\mathrm{C}_5^5$,两组选取人数之和为 $5$。

观察规律:同一行中的配对乘积

第 $5$ 行各数平方后求和,得到 $252$。注意先平方再相加,并不是先求行和再平方。

计数解释:把第二个因子换成互补选择

$\mathrm{C}_n^i=\mathrm{C}_n^{n-i}$。乘积就表示从两组各 $n$ 人中,分别选 $i$ 人和 $n-i$ 人。

总选取人数固定为 $n$,所以分类相加后等于 $\mathrm{C}_{2n}^n$。

推导证明:对称性连接范德蒙德

$$\mathrm{C}_{n}^{i}\mathrm{C}_{n}^{i}=\mathrm{C}_{n}^{i}\mathrm{C}_{n}^{n-i}$$

$$\sum_{i=0}^{n}\mathrm{C}_{n}^{i}\mathrm{C}_{n}^{n-i}=\mathrm{C}_{2n}^{n}$$

应用辨析:识别互补下标之和

看见同一行组合数的乘积,先尝试把一个因子用对称性改写,再检查两个下标的和是否固定。

注意

平方和不等于行和的平方;后者还包含不同下标之间的交叉乘积。

课堂小测

课堂小测

$\sum_{i=0}^{4}(\mathrm{C}_{4}^{i})^2$ 等于多少?

查看答案与解析

答案A

解析

$\mathrm{C}_8^4=70$。

辨析
  • B:$256$ 是行和的平方 $16^2$,包含交叉项
  • C:16 是第 4 行的行和,没有平方
  • D:两组人数合并为 $8$,结果是 $\mathrm{C}_8^4$。

相关专题:范德蒙德恒等式、对称性与互补选择、错位乘积求和。

专题 19

错位乘积求和

把平方和推广到同一行相隔 $r$ 个位置的乘积。

核心公式

$$\sum_{i=0}^{n-r}\mathrm{C}_{n}^{i}\mathrm{C}_{n}^{i+r} = \mathrm{C}_{2n}^{n-r}$$

$0\le r\le n$;$r=0$ 时就是平方和恒等式。

第 6 行中,绿色的 \mathrm{C}_6^0=1 与橙色的 \mathrm{C}_6^2=15 相隔两格;五个错位乘积求和为 495,等于紫色框中的 \mathrm{C}_{12}^4=\mathrm{C}_{12}^8。
图 1第 $6$ 行中,绿色的 $\mathrm{C}_6^0=1$ 与橙色的 $\mathrm{C}_6^2=15$ 相隔两格;五个错位乘积求和为 $495$,等于紫色框中的 $\mathrm{C}_{12}^4=\mathrm{C}_{12}^8$。

示例参数下:

$$15+120+225+120+15=\mathrm{C}_{12}^4=495$$

让第二个因子平移 $r$ 格

$i$ 第一个因子 第二个因子 乘积
$0$ $\mathrm{C}_6^0$ $\mathrm{C}_6^{2}$ $15$
$1$ $\mathrm{C}_6^1$ $\mathrm{C}_6^{3}$ $120$
$2$ $\mathrm{C}_6^2$ $\mathrm{C}_6^{4}$ $225$
$3$ $\mathrm{C}_6^3$ $\mathrm{C}_6^{5}$ $120$
$4$ $\mathrm{C}_6^4$ $\mathrm{C}_6^{6}$ $15$

$$\mathrm{C}_{6}^{0} \times \mathrm{C}_{6}^{2} = 15$$

以 $i=0$ 为例,利用对称性 $\mathrm{C}_6^2=\mathrm{C}_6^4$,两组选取人数之和为 $4$。

结果位于第 $12$ 行:$\mathrm{C}_{12}^4=495$;由对称性,它也等于 $\mathrm{C}_{12}^8$。

观察规律:同一行中的配对乘积

将第 $6$ 行下标相距 $2$ 的两个数相乘,再从左到右累加,总和为 $495$。

计数解释:把第二个因子换成互补选择

以 $r=2$ 为例,$\mathrm{C}_n^{i+2}=\mathrm{C}_n^{n-2-i}$。乘积就表示从两组各 $n$ 人中,分别选 $i$ 人和 $n-2-i$ 人。

总选取人数固定为 $n-2$,所以分类相加后等于 $\mathrm{C}_{2n}^{n-2}$。

推导证明:对称性连接范德蒙德

$$\mathrm{C}_{n}^{i}\mathrm{C}_{n}^{i+r}=\mathrm{C}_{n}^{i}\mathrm{C}_{n}^{n-r-i}$$

$$\sum_{i=0}^{n-r}\mathrm{C}_{n}^{i}\mathrm{C}_{n}^{n-r-i}=\mathrm{C}_{2n}^{n-r}$$

应用辨析:识别互补下标之和

看见同一行组合数的乘积,先尝试把一个因子用对称性改写,再检查两个下标的和是否固定。

注意

平方和不等于行和的平方;后者还包含不同下标之间的交叉乘积。

课堂小测

课堂小测

$\sum_{i=0}^{3}\mathrm{C}_{5}^{i}\mathrm{C}_{5}^{i+2}$ 等于什么?

查看答案与解析

答案A

解析

互补改写后总选取数为 $5-2=3$。

辨析
  • B:只有间距 $r=0$ 时结果下标才是 $n$
  • C:结果下标为 $n-r$,不是 $r$
  • D:两组总体合并为 $2n=10$。

相关专题:组合数平方和、范德蒙德恒等式。

专题 20

二项式定理与通项

每个括号选一次:组合数就是同类项出现的次数。

核心公式

$$(a+b)^{n} = \sum_{i=0}^{n}\mathrm{C}_{n}^{i}a^{n-i}b^{i}$$

$n$ 为非负整数;$a,b$ 为实数。零次幂作为多项式中的空乘积取 $1$(包括代入 $0$ 时)。

第 5 行绿底格 1,5,10,10,5,1 是二项式展开的系数;紫底格 \mathrm{C}_5^2=10 对应第 3 项的二项式系数。橙色描边另标出数值示例中的第 1 项。
图 1第 $5$ 行绿底格 $1,5,10,10,5,1$ 是二项式展开的系数;紫底格 $\mathrm{C}_5^2=10$ 对应第 $3$ 项的二项式系数。橙色描边另标出数值示例中的第 $1$ 项。

示例参数下:

$$(1+2)^5=1+10+40+80+80+32=243$$

一行组合数,生成一整条展开式

项数 项的表达式 $a=1,b=2$ 时的项值
第 $1$ 项 $\mathrm{C}_5^0a^{5}b^0$ $1$
第 $2$ 项 $\mathrm{C}_5^1a^{4}b^1$ $10$
第 $3$ 项 $\mathrm{C}_5^2a^{3}b^2$ $40$
第 $4$ 项 $\mathrm{C}_5^3a^{2}b^3$ $80$
第 $5$ 项 $\mathrm{C}_5^4a^{1}b^4$ $80$
第 $6$ 项 $\mathrm{C}_5^5a^{0}b^5$ $32$

$$\mathrm{C}_{5}^{0}a^{5}b^{0} = 1$$

第 $1$ 项的二项式系数为 $1$;代入 $a=1,b=2$ 后,项值为 $1$。

观察规律:把第 $n$ 行读成展开式系数

$(a+b)^5$ 的形式展开有 $6$ 项。取 $k=2$,对应第 $3$ 项:

$$T_{3}=\mathrm{C}_{5}^{2}a^{3}b^{2}$$

计数解释:每个括号选择 $a$ 或 $b$

把 $(a+b)^n$ 看成 $n$ 个括号相乘。要产生 $a^{n-i}b^i$,就需要从 $n$ 个括号中挑 $i$ 个取 $b$,其他取 $a$,恰好有 $\mathrm{C}_n^i$ 种选择。

推导证明:按选择 $b$ 的次数分类

$$T_{i+1}=\mathrm{C}_{n}^{i}a^{n-i}b^{i}$$

$i$ 从 $0$ 到 $n$,所有乘积按同类项合并,就得到二项式定理。令 $a=b=1$ 得行和,令 $a=1,b=-1$ 得交错和。

应用辨析:系数、二项式系数与项值

对 $(1+2x)^n$:第 $k+1$ 项为 $\mathrm{C}_n^k2^kx^k$;二项式系数为 $\mathrm{C}_n^k$,$x^k$ 的系数为 $2^k\mathrm{C}_n^k$。

注意

若展开 $(x^2+1/x)^n$,幂次是 $2(n-k)-k=2n-3k$。求常数项需要解幂次为 $0$,不能直接把 $k$ 当作 $x$ 的指数。

课堂小测

课堂小测

$(1+2x)^5$ 中,$x^2$ 的系数是多少?

查看答案与解析

答案A

解析

$\mathrm{C}_5^2\times2^2=10\times4=40$。

辨析
  • B:$10$ 只是二项式系数,还要乘 $2^2$
  • C:$2$ 的指数应为 $2$,不是 $1$
  • D:$x^2$ 对应 $k=2$,乘的是 $2^2$。

相关专题:行和与所有子集、交错和、范德蒙德恒等式、最大二项式系数。

交互动图单独打开 ↗