2026-08-04-Preview

2026-08-04-Preview · Probability Theory Ch1 Combinatorial Analysis（组合分析）

Ref: Lecture slides Ch1 · Ross Ch1 Combinatorial Analysis

Key Concepts

Term	Definition
Basic Principle of Counting（基本计数原理 / 乘法原理）	If experiment 1 has $n_1$ possible outcomes, experiment 2 has $n_2$ possible outcomes, …, experiment $r$ has $n_r$ possible outcomes, then there are $n_1\cdot n_2\cdots n_r$ total outcomes
Permutation（排列）	Number of permutations (ordered arrangements) of $n$ objects: $n!$; with $n_1,n_2,\dots ,n_r$ objects alike: $\frac{n!}{n_1!n_2!\cdots n_r!}$
Combination（组合）	Number of groups of $r$ objects from $n$ objects: $\frac{n!}{(n-r)!}$ if order matters; $\frac{n!}{(n-r)!r!}$ if order does not matter
Binomial coefficient（二项式系数）	Coefficients $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ in $(x+y{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^{n-k}$
Multinomial coefficient（多项式系数）	Dividing $n$ objects into $r$ groups of sizes $n_1,\dots ,n_r$: $\left(\genfrac{}{}{0ex}{}{n}{n_1,\dots ,n_r}\right)=\frac{n!}{n_1!\cdots n_r!}$

Per-Subsection: Definition & Examples

1.1 Counting and Probability（计数问题与概率）

Definition

$$P(\text{event})=\frac{\#\text{favorable outcomes}}{\#\text{total outcomes}}$$

Example: A room contains 1 man and 2 women; pick randomly.

• Pick 1 person: $P(\text{man})=\frac{1}{3}$.
• Pick 2 without replacement, exactly one man and one woman: all outcomes are $(M,W_1),(M,W_2),(W_1,W_2)$, so $P=\frac{2}{3}$.
• Key idea: probability problems reduce to counting the number of ways an event can occur.

1.2 Basic / Generalized Principle of Counting（计数基本原理）

Definition

If experiment 1 has $n_1$ possible outcomes, experiment 2 has $n_2$ possible outcomes, …, experiment $r$ has $n_r$ possible outcomes, then there is a total of $n_1\cdot n_2\cdots n_r$ possible outcomes of the $r$ experiments.

Example: 6-place license plates（6 位车牌）: first 3 places letters, last 3 digits, three cases of repetition restriction（重复限制）:

• Letters no repetition: $26\cdot 25\cdot 24\cdot 10\cdot 10\cdot 10=15,600,000$
• Digits no repetition: $26^3\cdot 10\cdot 9\cdot 8=12,654,720$
• Both no repetition: $26\cdot 25\cdot 24\cdot 10\cdot 9\cdot 8=11,232,200$
• Key idea: the number of choices at each step depends on whether the previous step “used up” an element.

1.3 Permutations（排列）

Definition

For $n$ objects, the number of permutations, i.e. ordered arrangements, of these $n$ objects is given by $n!$.

Permutations with objects alike: For $n$ objects, of which $n_1$ are alike, $n_2$ are alike, …, $n_r$ are alike, there are $\frac{n!}{n_1!n_2!\cdots n_r!}$ permutations.

Example: 10 textbooks (3 math, 3 physics, 2 chemistry, 2 biology), all books of the same subject must stay together.

• Order the 4 subjects: $4!$;
• Arrange within each subject: $3!\cdot 3!\cdot 2!\cdot 2!=144$;
• Total: $4!\times 144=3456$.
• Key idea: two-stage counting (subjects first, then within each); easy to forget the $4!$.

1.4 Combinations（组合）

Definition

The number of different groups of $r$ objects that can be formed from $n$ objects is $\frac{n!}{(n-r)!}$ if the order matters, and $\frac{n!}{(n-r)!r!}$ if the order does not matter.

Binomial theorem

$$(x+y{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^{n-k}$$

Method 1: Proof by induction

• Base case（归纳基始）: true at $n=1$: $$(x+y{)}^1=x+y=(\genfrac{}{}{0ex}{}{1}{0})x^0{y}^1+(\genfrac{}{}{0ex}{}{1}{1})x^1{y}^0$$
• Inductive step（归纳步骤）: assume it holds at rank $n-1$, then $$(x+y{)}^n=(x+y)(x+y{)}^{n-1}=(x+y)\sum _{k=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)x^k{y}^{n-1-k}$$ $$=\sum _{k=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)x^{k+1}{y}^{n-1-k}+\sum _{k=0}^{n-1}\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)x^k{y}^{n-k}$$
• Change of variables（换元）$l\leftarrow k+1$ in the 1st sum: $$(x+y{)}^n=x^n+\sum _{l=1}^{n-1}\left[\left(\genfrac{}{}{0ex}{}{n-1}{l-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{l}\right)\right]x^l{y}^{n-l}+y^n$$
• Pascal’s identity（帕斯卡恒等式）: $$\left(\genfrac{}{}{0ex}{}{n-1}{l-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{l}\right)=\frac{(n-1)!}{(l-1)!(n-1-l)!}\left(\frac{1}{n-l}+\frac{1}{l}\right)=\left(\genfrac{}{}{0ex}{}{n}{l}\right)$$
• Hence every coefficient is $\left(\genfrac{}{}{0ex}{}{n}{l}\right)$ — this is exactly Pascal’s triangle（帕斯卡三角）.

Method 2: Proof by combinatorics

• Introduce artificial labels（人为编号）on $x,y$ and consider the product $$(x_1+y_1)(x_2+y_2)\cdots (x_n+y_n)$$
• Expanding gives $2^n$ terms; e.g. for $n=2$: $$(x_1+y_1)(x_2+y_2)=x_1{x}_2+x_1{y}_2+y_1{x}_2+y_1{y}_2$$
• Among the $2^n$ terms, a term contains $k$ of the $x_i$‘s and $n-k$ of the $y_i$‘s; choosing which $k$ positions take an $x_i$ gives $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ such terms: $$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$$
• Setting $x_i=x$, $y_i=y$, each such term becomes $x^k{y}^{n-k}$, hence $$(x+y{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^{n-k}$$

Example: antennas（天线问题）— among $n$ antennas, $m$ are defective; no two defectives can be adjacent. Number of linear orderings?

• Arrange the $n-m$ good antennas first, creating $n-m+1$ gaps (including the ends);
• Place at most one defective per gap: choose $m$ of the gaps;
• Answer: $\left(\genfrac{}{}{0ex}{}{n-m+1}{m}\right)$; it is 0 if $m>n-m+1$.
• Key idea: gap method（插空法）— use good antennas as the skeleton, gaps constrain the defectives.

1.5 Multinomial Coefficients（多项式系数）

Definition

$$\left(\genfrac{}{}{0ex}{}{n}{n_1,\dots ,n_r}\right)=\frac{n!}{n_1!\cdots n_r!}(n_1+\cdots +n_r=n)$$

Same as the number of permutations of $n$ items with $n_1,n_2,\dots ,n_r$ alike（同 §1.3 的同类排列公式）。

Multinomial theorem

$$(x_1+\cdots +x_r{)}^n=\sum _{n_1+\cdots +n_r=n}(\genfrac{}{}{0ex}{}{n}{n_1,\dots ,n_r})x_1^{n_1}\cdots x_r^{n_r}$$

Example: knockout tournament, first round（淘汰赛首轮）— $n=8$ players are paired into 4 matches; each match has one winner. How many outcomes are possible for round 1?

• Labeled pairings: $\left(\genfrac{}{}{0ex}{}{8}{2,2,2,2}\right)=\frac{8!}{2^4}$; pairs are unordered, divide by $4!$: $\frac{8!}{2^4\cdot 4!}=105$ pairings;
• Each match has 2 outcomes, 4 matches: $105\times 2^4=\frac{8!}{4!}=1680$.
• Key idea: unlabeled groups ⇒ divide by permutations of group labels; multiply pairings by per-match outcomes.