Combinatorics and the Binomial Theorem组合学与二项式定理

If a task can be split into $k$ independent stages, and stage $i$ can be performed in $n_i$ ways, then the total number of ways to perform the task is若任务可分为 $k$ 个独立阶段，第 $i$ 阶段有 $n_i$ 种方式，则完成整任务的方式数为：

• Multiply, not add."乘"而非"加"。 AB Math 30-1 indicator 1.2 names this distinction explicitly: students must "explain, using examples, why the total number of possible choices is found by multiplying rather than adding the number of ways the individual choices can be made."AB Math 30-1 指标 1.2 明确点名："用例子解释为何总方式数应通过对各步方式数相乘，而非相加得到。"
• With or without replacement.是否放回。 With replacement: each stage has the same number of options (e.g. a 4-digit PIN from $\{0, \ldots, 9\}$ has $10^4 = 10\,000$ codes). Without replacement: each stage has one fewer option than the last (e.g. arranging $4$ distinct books on a shelf has $4 \cdot 3 \cdot 2 \cdot 1 = 24$ orderings).有放回：各阶段方式数相同（如 4 位 PIN 取自 $\{0, \ldots, 9\}$ 共 $10^4 = 10\,000$ 组）。无放回：每阶段比上一阶段少一种（如 $4$ 本不同书的排列共 $4 \cdot 3 \cdot 2 \cdot 1 = 24$ 种）。
• Tree-diagram backup.树状图补强。 When the multiplication is non-obvious, draw the first few branches of a tree and confirm the product (AB Math 30-1 indicator 1.1; MDM4U Counting and Probability also names tree diagrams).乘法不直观时，画出树的前几支并核对乘积（AB Math 30-1 指标 1.1；MDM4U Counting and Probability 同样点名树状图）。

• Permutation.排列。 An ordered selection of $r$ objects from $n$ distinct objects. Order matters: "ABC" and "ACB" count as different.从 $n$ 个不同元素中有序地选 $r$ 个。顺序要紧："ABC" 与 "ACB" 算作不同。
• Why $r \le n$.为何 $r \le n$。 AB Math 30-1 indicator 2.4 names this: $_nP_r$ is undefined for $r > n$ because you cannot choose more distinct objects than exist.AB Math 30-1 指标 2.4 指出：$r > n$ 时 $_nP_r$ 无定义，因为不能从有限集中选出比总数更多的不同元素。
• Special case $r = n$.特例 $r = n$。 $_nP_n = n!$ , the number of orderings of all $n$ distinct objects.$_nP_n = n!$ , 全部 $n$ 个不同元素的排列数。
• Identical elements (Math 30-1 indicator 2.6).含相同元素（Math 30-1 指标 2.6）。 If $n$ objects include $k_1$ of one type, $k_2$ of another, $\ldots$, $k_m$ of the last, then the number of distinguishable arrangements is若 $n$ 个元素中第 1 类 $k_1$ 个、第 2 类 $k_2$ 个、$\ldots$、第 $m$ 类 $k_m$ 个，则不同排列数为 $$ \frac{n!}{k_1! \, k_2! \cdots k_m!}. $$

• Combination.组合。 An unordered selection of $r$ objects from $n$ distinct objects. Order does not matter: $\{A, B, C\}$ and $\{C, A, B\}$ are the same combination.从 $n$ 个不同元素中无序地选 $r$ 个。顺序不要紧：$\{A, B, C\}$ 与 $\{C, A, B\}$ 算同一组合。
• Permutation $\to$ combination.由排列得组合。 Every $r$-combination corresponds to $r!$ permutations of the same $r$ objects. So divide $_nP_r$ by $r!$ to remove the over-counting.每个 $r$ 组合对应同 $r$ 个元素的 $r!$ 种排列，故用 $_nP_r$ 除以 $r!$ 消除重复计数。
• Decision rule.判别准则。 Ask: does order matter? If yes , permutation. If no , combination. AB Math 30-1 indicator 3.1 expects students to explain this distinction with examples.自问：顺序要紧吗？要紧 , 排列；不要紧 , 组合。AB Math 30-1 指标 3.1 要求学生用例子解释此区别。
• Notation.记号。 $\binom{n}{r}$ ("$n$ choose $r$") is the modern notation that AP / IB / university courses prefer; $_nC_r$ is the calculator-key form. They are identical.$\binom{n}{r}$（读作"$n$ 选 $r$"）为 AP / IB / 大学课程偏好的记号；$_nC_r$ 是计算器按键形式。两者相同。

• Symmetry.对称性。 Choosing $r$ from $n$ is the same as choosing the $n - r$ to leave behind , one decision, two interpretations. AB Math 30-1 indicator 3.5 names this identity explicitly.从 $n$ 中选 $r$ 等同于选出剩下不取的 $n - r$ , 一个决定，两种诠释。AB Math 30-1 指标 3.5 明确点名此恒等式。
• Pascal's rule.帕斯卡规则。 Each entry of Pascal's triangle is the sum of the two entries directly above. Combinatorial proof: any $(r+1)$-subset of an $(n+1)$-set either contains the last element (then choose $r$ from the first $n$, giving $\binom{n}{r}$) or omits it (choose $r+1$ from the first $n$, giving $\binom{n}{r+1}$).帕斯卡三角形每项等于其正上方两项之和。组合论证：$(n+1)$ 元集合的任一 $(r+1)$ 子集要么含最末元素（则从前 $n$ 中选 $r$，共 $\binom{n}{r}$ 种），要么不含（从前 $n$ 中选 $r+1$，共 $\binom{n}{r+1}$ 种）。
• Building the triangle.逐行构造。 AB Math 30-1 indicator 4.2 expects students to "explain how to determine the subsequent row in Pascal's triangle, given any row" , pure addition, no factorial. Row $0$ is "$1$"; row $1$ is "$1$ $1$"; each subsequent row begins and ends with $1$ and fills the middle by adding adjacent pairs.AB Math 30-1 指标 4.2 要求学生"由任一行说明如何确定帕斯卡三角形的下一行" , 纯加法，无需阶乘。第 $0$ 行为"$1$"；第 $1$ 行为"$1$ $1$"；其后每行首尾为 $1$，中间项由上一行相邻两数相加而得。

• Coefficients come from row $n$ of Pascal's triangle.系数即帕斯卡三角形第 $n$ 行。 AB Math 30-1 indicator 4.3 says verbatim: "relate the coefficients of the terms in the expansion of $(x + y)^n$ to the $(n + 1)$ row in Pascal's triangle" (because rows are zero-indexed).AB Math 30-1 指标 4.3 原文："把 $(x + y)^n$ 展开式各项的系数与帕斯卡三角形第 $(n+1)$ 行相对应"（因行从 $0$ 开始计数）。
• Why combinations?为何是组合？ When you multiply out $(a+b)(a+b)\cdots(a+b)$ ($n$ factors), each term in the expansion chooses $b$ from $r$ of the factors and $a$ from the other $n-r$. The number of ways to pick which $r$ factors contribute $b$ is $\binom{n}{r}$. (Math 30-1 indicator 4.4 names exactly this combinatorial argument.)展开 $(a+b)(a+b)\cdots(a+b)$（共 $n$ 个因式）时，每一项都在某 $r$ 个因式取 $b$，其余 $n-r$ 个取 $a$。从 $n$ 个因式中选出"贡献 $b$"的那 $r$ 个，共 $\binom{n}{r}$ 种 , 这正是 Math 30-1 指标 4.4 所述论证。
• Total number of terms.总项数。 $(a + b)^n$ has $n + 1$ terms, indexed by $r = 0, 1, 2, \ldots, n$. Exponents on $a$ go down, on $b$ go up, summing to $n$.$(a + b)^n$ 共有 $n + 1$ 项，下标 $r = 0, 1, 2, \ldots, n$。$a$ 的指数递减，$b$ 的递增，两指数之和恒为 $n$。
• General term.通项。 $T_{r+1} = \binom{n}{r} a^{n-r} b^r$. The $r=0$ term is $T_1$, the $r=1$ term is $T_2$, and so on , the "$r+1$" indexing is standard in most textbooks.$T_{r+1} = \binom{n}{r} a^{n-r} b^r$。$r=0$ 项是 $T_1$，$r=1$ 项是 $T_2$，依此类推 , 教材中通常用 "$r+1$" 编号。

1. Write down the general term $T_{r+1} = \binom{n}{r} a^{n-r} b^r$ with $a$ and $b$ taken from the bracket.写下通项 $T_{r+1} = \binom{n}{r} a^{n-r} b^r$，其中 $a$、$b$ 取自括号。
2. Simplify the powers and isolate the exponent on $x$.化简各幂，整理出 $x$ 的总指数。
3. Set the exponent equal to the target value and solve for $r$. Substitute that $r$ back into the general term.把 $x$ 指数等于目标值，解出 $r$，再代回通项。

• Algebraic derivation.代数推导。 Set $a = b = 1$ in the Binomial Theorem: $(1 + 1)^n = \sum \binom{n}{r} \cdot 1^{n-r} \cdot 1^r = \sum \binom{n}{r}$, and the left side is $2^n$. Set $a = 1, b = -1$: $(1 + (-1))^n = \sum \binom{n}{r}(-1)^r$, and the left side is $0^n = 0$ for $n \ge 1$.在二项式定理中令 $a = b = 1$：$(1 + 1)^n = \sum \binom{n}{r} \cdot 1^{n-r} \cdot 1^r = \sum \binom{n}{r}$，左边即 $2^n$。再令 $a = 1, b = -1$：$(1 - 1)^n = \sum \binom{n}{r}(-1)^r$，左边为 $0^n = 0$（$n \ge 1$）。
• Combinatorial reading of the first identity (double counting).第一个恒等式的组合诠释（双重计数）。 $\binom{n}{r}$ counts subsets of an $n$-set with exactly $r$ elements. Summing over all $r$ counts all subsets, partitioned by size. Independently, the total number of subsets of an $n$-set is $2^n$ (each element is "in" or "out", $2$ choices, $n$ independent stages, multiplication rule). Two counts of the same set $\Rightarrow$ identity.第一个恒等式的组合解释：$\binom{n}{r}$ 是 $n$ 元集恰含 $r$ 个元素的子集数；对所有 $r$ 求和即按大小划分计数全部子集。另一方面，$n$ 元集的子集总数为 $2^n$（每个元素"取或不取"两种，$n$ 个独立阶段，乘法原理）。同一集合的两种计数 $\Rightarrow$ 恒等。
• Combinatorial reading of the second identity.第二个恒等式的组合诠释。 For $n \ge 1$, the number of even-sized subsets of an $n$-set equals the number of odd-sized subsets. (Pair any subset $A$ with $A \triangle \{e\}$ for a fixed element $e$ , this is a bijection between even-size and odd-size subsets.)$n \ge 1$ 时，$n$ 元集中偶数大小子集数 = 奇数大小子集数。（固定一元素 $e$，把任一子集 $A$ 与对称差 $A \triangle \{e\}$ 配对 , 这是偶 / 奇大小子集间的双射。）