计数与概率 · 方法讲解

对应计数法

把难数的对象变成好数的对象，先证明双向可逆，或核对固定原像数。

下载视频 ↗

有间隔限制，能换一种对象数吗？

从整数1至8中选3个不同的数，要求任意两个不相邻，不计选取顺序。有多少种选法？例如(1,4,7)合法，(1,2,7)不合法。演示先追踪一个对象的去向，再核对整体计数。

固定示例：原组(1,4,7)，从1至8中选3数，互不相邻。

第0/4步：先把原组排成a<b<c，选(1,4,7)追踪变换。原题整体计数尚未推出。

原理：怎样才有资格“换对象”？

学习目标：构造正向与逆向规则，说明不重不漏；当规则会丢失标记时，确定每个目标对象有几个原像。需要会大小比较、加减、乘法原理与简单组合数。

这里的对象是一种完整选法。集合A、B分别收集原题与新题的所有合法对象。映射（mapping）f给每个A中的对象指定一个B中的对象。原像（preimage）是变换后落到某个目标对象的原对象。

一一对应（bijection）

先验证f对所有原对象都有定义且落在B中。再写逆规则g，使g(f(a))=a、f(g(b))=b对两边全部对象都成立。于是既没有两个原对象挤到一起，也没有新对象被漏掉。

|A| = |B|

固定原像数

若每个B对象恰好有m个A原像，且m为同一个正整数，则A被分成|B|份，每份m个。由此得到除法计数，不必强求一一对应。

|A| = m|B|，|B| = |A|÷m

|A|表示有限集合A中的对象数。写出一个看似合理的公式不是证明：先交代两边对象、合法性、还原规则或每组的原像数，最后计算。

两道完整例题

例题一 · 互不相邻的选数（自拟）

题目：从1至8选3个不同整数，任意两个不相邻，且不计顺序，求选法数。

把对象写清。每个原组选成唯一升序三元组(a,b,c)，满足1≤a、b−a≥2、c−b≥2、c≤8。
正向压缩。设(x,y,z)=(a,b−1,c−2)。此时1≤x<y<z≤6，所以新对象是1至6中的一个三元素子集。
反向还原。对任意1≤x<y<z≤6，取(a,b,c)=(x,y+1,z+2)。两个差至少2，且1≤a、c≤8，确为原题合法对象。
互相撤销。先减后加回同一偏移，每个坐标还原。先加后减也还原。因此所有新对象都被覆盖，且没有重复对应。
计算新题。依次选3个不同数有6×5×4种。每个三元素子集恰对应3×2×1=6种排列，所以选法为120÷6=20种。

C(6,3) = 6×5×4÷(3×2×1) = 20

C(N,k)表示从N个不同对象中不计顺序选k个的组合数。先排序是统一写法，不是额外选择，因此不能把20再乘6。

推广：从n个位置选k个，互不相邻

若1≤a₁<…<aₖ≤n，且相邻所选数之差至少2，则令bᵢ=aᵢ−(i−1)。得到1≤b₁<…<bₖ≤n−k+1；逆规则为aᵢ=bᵢ+(i−1)。所以n≥2k−1时，选法数为C(n−k+1,k)。这里n、k为整数且k≥1。

存在性边界：n<2k−1时不可能选出k个数，计0种，不能不加说明地套不满足取值范围的组合数。若k=0，则另规定空选法1种。该压缩证明针对一条线，不能直接用于首尾也相邻的环形位置。

例题二 · 指定代表，再忘掉代表（自拟）

题目：甲、乙、丙、丁、戊5人中选3人组成一组，不分职务、不计顺序。不用直接写C(5,3)，利用“指定代表”求组数。

先数带标记对象。选代表有5种，再从剩下4人中选2名同伴，有4×3÷2=6种。共5×6=30个“团队＋代表”。
忘掉代表。把“团队＋代表”送到普通团队。对任何三人组，每一名成员都可以是代表，且只有组内3人可当代表，所以每个目标恰有3个原像。
统一除3。30个带标记对象被分成每份3个的等大组，因此普通团队有30÷3=10组。

甲代表：甲乙丙乙代表：甲乙丙丙代表：甲乙丙→ 同一组{甲,乙,丙}

这个映射不是双向可逆：只看普通团队，不知道原先代表是谁。可以做除法，是因为全部目标团队都恰有3个原像。

迁移练习：改限制，重新证明

练习一 · 两数之间至少空两个整数（自拟）

从1至10选3个数，任意两数之差至少3，不计顺序。有多少组选法？请给出可逆变换和边界验证。

查看完整解析

升序写作(a,b,c)，令(x,y,z)=(a,b−2,c−4)。因相邻原数至少差3，新数至少差1，且1≤x<y<z≤6。任意1至6中的三元素子集，反向依次加0、2、4后得到1至10中间距至少3的合法原组。两个操作互相撤销，故有C(6,3)=20种。

更一般，要求相邻所选数之差至少d（正整数），偏移应是0、d−1、2(d−1)…，不是每项都减d−1。压缩后的范围是1至n−(d−1)(k−1)。至少需要n≥1+d(k−1)才可选出k个数。

练习二 · 两个不同职务（自拟）

6名不同学生中选3人组成一队。先指定队长和副队长两种不同职务，余下一人为普通队员；再忘掉职务。带职务的方案有多少？普通三人队有多少？为何不能只除3？

查看完整解析

队长6种，副队长5种，普通队员4种，共6×5×4=120种带职务方案。任何固定三人队，队长3种，副队长2种，普通队员随之确定，恰有3×2=6个原像。忘掉全部职务后有120÷6=20队。

只除3仅消掉“谁当队长”这一层标记，尚未消掉“谁当副队长”。核对原像时必须把所有被忘掉的信息计算完整。

边界反例与回顾

原像数不固定，不能统一除

只允许{甲}、{乙}、{甲,乙}这3个团队。给每队指定一名组内代表，标记对象数为1+1+2=4。忘掉代表后有3个组；若统一除2得到2，显然漏组。应先分成单人组和双人组，分别按1和2的原像数计数，再相加。

只有正向不够：“把数都乘2”能把1至3送进1至6，但1、3、5等目标未被覆盖，不能据此说两边数量相等。
不同对象不能压成同一个：把(a,b)变成a+b会丢掉组成信息，除非再证明各和的原像数相同，否则不能直接除。
次序不能混淆：先定义是否计顺序；排序后每个子集只有一种标准写法。
线形与环形不同：线形压缩不自动处理首尾也相邻的条件。

解题检查表：原对象是什么？新对象是什么？正向一定合法？逆向是否对每个新对象成立？两个操作能否撤销？若不能，是否每个目标恰有同一个正整数m个原像？核对完再写等式。

S班为本项目的内容深度编排，不代表当地官方课纲。全部例题为自拟有限集合题；公式由正文证明并作独立精确计算和穷举核对。图示只展示离散对象的变化，不作为完备性证明。

逐章回看

文字稿默认展开，点击标题可定位视频。章节时间依据实际旁白时间轴。

从一到八选三个数，任意两个不相邻。不计选取顺序，怎样数得不重不漏？

把三个数从小到大排列。第一个不变，第二个减一，第三个减二，压缩必须留出的间隔。

例如一、四、七，变成一、三、五。相邻原数至少差二，压缩后仍至少差一。

反过来，从一到六任取三个不同数，按顺序加零、一、二，就还原为一到八中互不相邻的三个数。

两个操作互相撤销，每一组都有唯一来处和去处。这才证明一一对应，而不是只看几个例子。

所以原题等于从六个数中选三个。六乘五乘四，再除以六种排列，得到二十组。

再看五人中选三人并指定一名代表。先选代表，再选两名同伴，共三十种。

忘掉代表后，同一个三人组恰好来自三种标记。因此普通三人组有三十除以三，等于十组。

但单人组只有一种代表，双人组有两种代表。原像数不固定，就不能统一除以二。

对应计数，先定义对象，再写正向与逆向；不能逆转时，逐个核对原像数是否相同。