计数、组合数学与有限概率

十条记录选三条用于评估，若结果是无序子集，有 120 种；若三条分别担任第一、第二、第三审核人等不同角色，有 720 种。输入看似相同，结果区别不同。计数公式只对明确模型正确。

先问结果包含什么、顺序是否重要、同一对象能否重复、不同构造是否代表同一结果，再用加法、乘法、双射与补集证明公式。概率还需要抽样规则，有限集合不自动均匀。

回忆检查：构造小笛卡尔积、列幂集、解释双射与分类证明。按需复习集合和证明。计数是非负整数，本模块只讨论有限结果；后续概率更详细区分概率与频率。

加法规则计数不交选项：A、B 不交时 $|A\cup B|=|A|+|B|$。竖线这里是有限基数，不是绝对值。重叠成员会被加两次，必须分成真正不交情况或在第 5 节修正。

乘法规则用于每个第一选择都有相同数量后续选择的阶段。第一阶段 a 种，各有 b 个允许延续，路径数 ab；独立选项集是笛卡尔积基数。计数阶段并不自行断言概率独立，它描述允许构造树；概率独立是抽样模型额外性质。

分支数量不同应相加，不能假定共同因子。两个任务各允许三位工人，一个只允许一位，共七种任务—工人配对，不是九。若每任务都允许三人，乘法才是另一个正确模型。

双射把难计集合一一对应到易计集合。须验证每个允许结果恰好一个表示，每个允许表示都产生结果。遗漏或重复使对应不能证明计数相等。第 4 节隔板法是例子。

构造计数也需范围明确。叶应是完整结果，不是部分选择。若丢弃顺序后不同路径变同一结果，叶计数会过计无序模型。因此有序选择树不能未经调整就计子集。

不选择任何位置有一个空序列，不是零个。零阶段的空乘积为一；实际某阶段没有可选项则所有构造失败，含零因子的积为零。这两种“空”不同。

CS 决策路径描述配置、串、分配与搜索空间。空间大小不等于每个算法耗时，算法可利用结构或只检查部分。AI 数据划分取决于记录是否不同、组是否具名、是否要求同主体记录同组。任意记录子集公式不会自动尊重主体约束。

从 n 个不同对象无放回选 r 个有序对象：

各位置可选数逐次减一。阶乘是至 n 的正整数积，$0!=1$。全排列有 n!，选择零个有一个空结果，r>n 无放回则零，阶乘公式只声明于允许范围。

标签相同且不可区别时，不同具名排列可表示同一标签串。A、A、B 只有 AAB、ABA、BAA 三种。暂给两个 A 命名得到六，每个标签串恰好两个表示，所以除共同倍数给 $3!/2!=3$。

一般 N 个对象、k 类标签次数 $n_1,\ldots,n_k$，总和 N，完整标签排列数为 $N!/(n_1!\cdots n_k!)$。分子计暂时具名对象，各同标签内部交换不改变标签串，每个串有相同内部交换积。固定次数与完整排列是前提。

不能随意除一个对称因子，须检查每结果表示数量相同。A、A、B 的部分二项选择中 AA 有一个具名位置构造，AB 有两个。三构造除猜测二并不得到正确的两个结果。

不同的含义取决于问题。同类别两记录通常仍是不同记录，交换具名角色改变记录结果，即使标签串不变。只观察类别会合并多个记录选择；转向概率前必须分开底层结果与表示。

放回有序公式 $n^r$ 也要求每位 n 个允许选项。后续依赖先前时，应按实际分支计。密码禁止重复或必须含数字引入约束，n! 与 $n^r$ 不自动处理，先定义构造再选公式。

边界检查 r=0、1、n、r>n 可揭错误。全标签相同的 N 对象只有一串，$N!/N!=1$。得到零或 N! 表示区别模型不同或有建模错误。

无序 r 元子集是组合，数为二项式系数：

每个不同对象的 r 子集恰有 r! 个有序排列，因此将 $P(n,r)$ 除此共同数，每子集一次。这是等表示倍数论证，不是脱离模型的公式。基本组合不保留顺序且禁止重复。

补集把 r 子集双射到 n−r 子集，故 $\binom nr=\binom n{n-r}$，用固定 n 元全集。$\binom n0=\binom nn=1$ 分别计空与全；n>0 时不表示它们是同一对象。

帕斯卡恒等式区分一个具名 x：r 子集或不含 x，有 $\binom{n-1}r$；或含 x，其他成员有 $\binom{n-1}{r-1}$。两情况不交且穷尽，故

n≥1 时将负选择数或超过非负上标的二项系数定义为零，就包含边界。分类证明解释恒等式与递推，不只是约掉阶乘。

二项式定理连接子集与代数：

n 个因子中，恰 r 个位置取 b、其余取 a，有 $\binom nr$ 个位置子集产生该单项式。零次幂两边一，用空乘积。这里 a、b 是可交换标量；矩阵顺序有意义，需额外条件。

取 a=b=1，得 $2^n=\sum_r\binom nr$，按不交子集大小计幂集，连接模块 03 的选入/不选入。两个有依据的方法计同一集合称双重计数证明。

两具名组中每记录恰属一组，选 r 决定补组。固定大小训练、验证、测试三组用多项式计数而非单个组合数；主体、时间与资格限制又减少允许划分。正确无约束数不自动是应用数。

连续均匀无放回选择后丢弃顺序可生成均匀子集：每有序序列等权，每子集恰 r! 个序列，合并权重相同。两性质都需要。若某阶段偏好某记录，即使总返回 r 个不同记录，也可使子集有偏。应把“随机”改成明确机制再赋概率。

普通集合不记录次数：{A,A,B} 与 {A,B} 同集。多重集保留两个 A、一个 B，可用次数元组或排序标签列表表示。探索器用双括号表示多重集，与子集花括号区别。规范排序去顺序却保留重复；再转集合会丢另一区别并改变计数。把表示作枚举键前先检查是否符合结果定义。

n 个相同任务给 k 位具名工人，即非负整数元组 $(x_1,\ldots,x_k)$ 和为 n。任务不可区别、工人可区别、允许零，数为

隔板法（stars and bars）用 n 星代表任务、k−1 板分隔各工人份额。板可在端点或相邻，表示零。共 n+k−1 位置，选板位置唯一决定字符串；每分配也唯一产生字符串，双射证明公式。

n 种类型无序选 r 个允许重复，是同类非负计数：$x_i$ 为类型 i 次数，总 r，数 $\binom{n+r-1}r$，n≥1。保留顺序则 $n^r$。丢顺序的表示倍数随重复变化，不能简单除 r!。

每工人至少一，可写 $y_i=x_i-1\ge0$，剩 n−k，n≥k 时数 $\binom{n-1}{k-1}$，否则零。一般下界 $l_i$ 减去总下界，先检查可行再算阶乘。

上界不能这样直接消除。五任务、三工人、每人至多二：21 无约束分配中，指定工人至少三时减三，剩二任务给三人，有六。三禁集不可能两者重叠，因为至少六任务才行。有效 $21-3\cdot6=3$，即 (2,2,1) 的排列。

这用补集与容斥，下一节展开。正确公式可能正确计其模型却解错题。上下界、工人具名与任务可区别性都是结构前提。

若工人不具名，(2,1,2) 与 (1,2,2) 可能同结果，具名公式过计。整数分拆是另一问题，不在核心。不能自动除 k!，相等份额与全不同份额的表示倍数不同。

零任务且 k≥1 有一个全零分配，与公式一致；要求正份额则无。零工人不在公式论域，可另规定零任务时一个空分配。异常域应明确。

A、B 重叠时，加大小使交集计两次，减一次得 $|A\cup B|=|A|+|B|-|A\cap B|$。四成员区域：仅 A、仅 B 各贡献一；交区贡献 $1+1-1=1$；都不属于贡献零。解释修正比只背公式有用。

三集合加单项、减两两交、加三交：

三者都属的成员先三、减三、加一；恰属二者贡献二减一；恰属一贡献一。这些不交情况覆盖证明。更多集合交项交替，小模型有时枚举更简单。

补集计数从总数减所求反面。至少一个碰撞的反面是全部桶不同，更易计。两情况应在共同全集中不交且穷尽；只补不完整失败列表会遗漏无效情况。

抽屉原理（pigeonhole principle）给保证而非概率。n 对象放 m 箱且 n>m，至少一箱有两个。若每箱至多一，总数至多 m，矛盾。m>0 时一般某箱至少 $\lceil n/m\rceil$，否则达不到总数。

五项放四桶必碰撞，无论规则与均匀性。三项四桶可碰却非必，可有不同桶。计数与抽样描述概率；容量未超时抽屉不提供保证。高概率与确定不同。

模块 04 的分类与反证支撑工具。容斥追踪每成员情况的系数，抽屉假设所有箱不足再推总数矛盾。新约束改变可能情况时不能被简短公式遮蔽。

不同容量 $c_i$ 的箱，超过总容量必某处溢出，是同一反证。不指出哪箱；少于总容量也不保证具体分配无溢出。可行分配存在与所选分配行为不同。

选择最易且有依据的计数：小重叠减交，至少一个看零个补，必重复比较容量。先命名数量并检查边界，常比做大算术更快揭模型错误。

有限样本空间 $\Omega$ 含模型全部结果，事件 E 是子集。均匀模型给每结果 $1/|\Omega|$，于是 $\Pr(E)=|E|/|\Omega|$。比值以前提等可能为条件，有限结果集本身不分配概率。

不等概率需给非负权重 $p_\omega$ 总和一，$\Pr(E)=\sum_{\omega\in E}p_\omega$。确定规则极端地给一结果一、其余零。计可能结果数不能区别它与均匀抽取，机制必须纳入模型。

k 项独立均匀选 m 桶，$0\le k\le m$ 时无碰撞 $\prod_{i=0}^{k-1}(m-i)/m$，补得碰撞。k=0 空积一，碰撞零；k>m 抽屉保证，与均匀无关。真实哈希在固定数据上未必独立均匀，公式是模型计算，不自动描述每实现。

独立使完整三元组概率为阶段概率积 $(1/4)^3$。若所有项复制同一个随机均匀桶，每项单独均匀，却相依且三项必碰。均匀边缘不保证独立联合模型。

合并表示也破坏均匀性。A、A、B 三个具名位置均匀选无序二位置，三个等可能对，一个给 AA，两个给 AB，观察概率 1/3 与 2/3。不能把 {AA,AB} 当均匀。映射到观测时，把全部原像权重相加保存概率。

模拟抽样指定机制并报告频率，可检查预测与实现，有限频率不必等于精确概率。固定种子复现一次运行，不把样本变成枚举。后续研究抽样误差与集中；这里分开报告精确数、模型概率、样本比例。

实验穷尽 64 元组，再按同模型抽一万次。改变权重、相关性或碰撞定义，就改变机制或事件，应重新计算。接近公式的图不解释模型为何适用，比较数字前写前提。

这些基础支持搜索空间、碰撞、数据划分与有限不确定性。共同习惯是先定义结果再算；概率还需先定义选择机制再谈机会。这是本模块的核心结业能力。

Python 3.11 或更新，无需包，见入门。itertools 构造有限序列与子集，math.comb 供精确整数参照，Fraction 保留精确概率。先解释结果模型。每次十分：预测三、计数/模型解释四、变化或故障三。

四十分钟：预测二进制串、六有序对、三子集、五任务分配，运行后指出每行的不同标准。解释零选择。把具名二位置改为无序无放回并证明除二。十选三枚举确认 120 与 720，但不替代推导。

下载 lab1_selections.py

"""Count ordered, unordered, and repeated choices over small explicit domains."""
from itertools import combinations, permutations, product
from math import comb, factorial


def main():
    binary = ["".join(bits) for bits in product("01", repeat=4)]
    assert len(binary) == 2 ** 4
    print("Length-four binary strings:", len(binary))
    print("Ordered two from ABC:", ["".join(p) for p in permutations("ABC", 2)])
    print("Unordered two from ABC:", ["".join(p) for p in combinations("ABC", 2)])
    for n, r in ((3, 2), (5, 0), (5, 3), (10, 3)):
        ordered = len(list(permutations(range(n), r)))
        unordered = len(list(combinations(range(n), r)))
        assert ordered == factorial(n) // factorial(n - r)
        assert unordered == comb(n, r)
        print(f"n={n}, r={r}: ordered={ordered}, unordered={unordered}")
    allocations = [(a, b, 5 - a - b) for a in range(6) for b in range(6 - a)]
    assert len(allocations) == comb(7, 2)
    print("Five identical tasks across three named workers:", len(allocations))
    print("First five allocations:", allocations[:5])


if __name__ == "__main__":
    main()

Length-four binary strings: 16
Ordered two from ABC: ['AB', 'AC', 'BA', 'BC', 'CA', 'CB']
Unordered two from ABC: ['AB', 'AC', 'BC']
n=3, r=2: ordered=6, unordered=3
n=5, r=0: ordered=1, unordered=1
n=5, r=3: ordered=60, unordered=10
n=10, r=3: ordered=720, unordered=120
Five identical tasks across three named workers: 21
First five allocations: [(0, 0, 5), (0, 1, 4), (0, 2, 3), (0, 3, 2), (0, 4, 1)]

四十分钟，第 6 节后：预测 64 元组、40 碰撞、5/8。运行比较样本比例，种子复现而不证明频率等于概率。改为五项四桶，无碰数须零、必碰；应更新无碰公式，不能保留三项表达式。讨论相关机制为何使独立公式失效。

下载 lab2_collisions.py

"""Uniform independent bucket choices: exact enumeration and a seeded sample."""
from fractions import Fraction
from itertools import product
from random import Random


def main():
    buckets, items = 4, 3
    outcomes = list(product(range(buckets), repeat=items))
    collisions = sum(len(set(outcome)) < items for outcome in outcomes)
    exact = Fraction(collisions, len(outcomes))
    no_collision_count = buckets * (buckets - 1) * (buckets - 2)
    assert exact == 1 - Fraction(no_collision_count, buckets ** items)
    print("Model: 3 named items choose independently and uniformly among 4 buckets.")
    print("Total outcomes:", len(outcomes), "collision outcomes:", collisions)
    print("Exact probability:", exact, "=", float(exact))
    rng = Random(2026)
    trials = 10000
    observed = 0
    for _ in range(trials):
        outcome = [rng.randrange(buckets) for _ in range(items)]
        observed += len(set(outcome)) < items
    estimate = observed / trials
    print(f"Seed=2026, trials={trials}, observed collision fraction={estimate:.4f}")
    print("A sampled fraction is not the exact probability or a collision guarantee.")


if __name__ == "__main__":
    main()

Model: 3 named items choose independently and uniformly among 4 buckets.
Total outcomes: 64 collision outcomes: 40
Exact probability: 5/8 = 0.625
Seed=2026, trials=10000, observed collision fraction=0.6188
A sampled fraction is not the exact probability or a collision guarantee.

四十分钟：预测 A、A、B 的完整标签串与二项倍数。解释全排列除二有效，而两观测各一半无效。运行保存两概率，描述三个等可能位置对映到两标签结果。改为 A、B、C，映射不合并位置对，所以各观察等权。

下载 lab3_repeated_labels.py

"""Distinguish named positions from repeated labels and preserve sampling weights."""
from collections import Counter
from fractions import Fraction
from itertools import combinations, permutations
from math import factorial


def main():
    labels = ("A", "A", "B")
    raw = list(permutations(labels))
    unique = sorted({"".join(outcome) for outcome in raw})
    assert len(raw) == 6 and len(unique) == factorial(3) // factorial(2)
    print("Named-position permutations:", len(raw))
    print("Distinct label strings:", unique, "count=", len(unique))
    selected = Counter("".join(sorted(pair)) for pair in combinations(labels, 2))
    print("Uniform pair of named positions; label multiplicities:", dict(sorted(selected.items())))
    total = sum(selected.values())
    for outcome, count in sorted(selected.items()):
        print(" ", outcome, "probability=", Fraction(count, total))
    print("Two possible label outcomes are not automatically equally likely.")
    print("Repair the count by defining whether positions, records, or labels are distinct.")


if __name__ == "__main__":
    main()

Named-position permutations: 6
Distinct label strings: ['AAB', 'ABA', 'BAA'] count= 3
Uniform pair of named positions; label multiplicities: {'AA': 1, 'AB': 2}
  AA probability= 1/3
  AB probability= 2/3
Two possible label outcomes are not automatically equally likely.
Repair the count by defining whether positions, records, or labels are distinct.

练习 1–12 共 110 分钟、每题五分；扩展额外 25 分钟。先给结果与前提，再算；错误模型的正确数不能满分。

九自动选择，书面模型解释自评供剩一分。反馈提醒计数前提。

必读十五分钟：在 MIT Mathematics for Computer Science 教材中阅读乘法、加法、子集计数，先说明一例顺序与重复再选公式。

必读二十分钟：阅读容斥与有限概率介绍，指出等可能假设位置，按成员情况重述重叠修正，区别计数与抽样概率。

选读：比较官方 itertools 组合迭代器 的顺序与放回约定，查看 math.comb 的精确整数参照。推导、例子与图原创。

结果定义决定计数：不交选择、构造分支或双射。有序、子集、多重集保留不同区别。容斥修重叠、补集计简单反面、抽屉给容量保证。概率增加权重，均匀才支持计数比。

结业任务：推导十选三有序与无序，证明帕斯卡，计约束任务分配，解释独立碰撞及相依反例。练习六十、实验三十、测验十分。算前写前提，反馈后修复区别。

模块 06 研究和、增长、递推。先解释搜索空间计数为何不自行确定某算法操作数，保留有限和归纳与乘法论证。