第36课 — 计数基本原理

PFC 与树

陈述

若一实验由 $k$ 个连续独立步骤组成，第一步 $n_1$ 种结果，第二步 $n_2$ 种，...，第 $k$ 步 $n_k$ 种，则总结果数为： $N = n_1 \cdot n_2 \cdots n_k$

加法原理（替代）

若任务可由方法 A（$m$ 种方式）或方法 B（$n$ 种方式）完成（互斥），总数为 $m + n$。

典型例

4 字符密码：每位 A-Z（26 选项）。总数：$26^4 = 456\,976$。

可能性树

每步"分支"——树有 $n_1$ 根，每根 $n_2$ 子节点，等。叶子 = 总结果数。

限制——"无重复"

若鞋不能重复，第一双 5 选项，第二双 4，第三双 3——无重复组合。推广为排列（第37课）。

集合间的函数

• $f: A \to B$ 全函数数，$|A| = m, |B| = n$：$n^m$。
• 单射函数（$f: A \to B$，$m \leq n$）：$n!/(n-m)!$（排列）。
• 双射函数（$m = n$）：$n!$（完全排列）。