第4卷第3章 171亿7986万9184份孤独

从四张卡片的排列树出发，推导排列数、组合数与重复元素计数，再把二项式、帕斯卡三角形和位模式统一到2^n，解释34比特标题数字与指数爆炸。

学习目标

能用树形图和乘法原理解释排列数，并从具体示例推广到 n! 与有重复元素的计数
能区分排列与组合，推导 P(n,k)、C(n,k) 以及相同元素排列的除重理由
能把二项式系数、帕斯卡递推和比特模式分类统一为 Σ C(n,k)=2^n
能计算指数增长的规模边界，解释为什么33比特不足而34比特可以为100亿个对象编码

从四张卡片开始：走向三百多亿条岔路

本章标题不是随意放大的数字：

2^{34}=17\,179\,869\,184.

中文读作171亿7986万9184，“171亿7986万9184份孤独”由此得名。要理解它为什么与“孤独”并列，必须先从更小的数字开始。周六，尤里在新开的书店遮住“我”的眼睛，又把人拉到楼顶。她不满足于只会套排列公式，因为班里“那家伙”问的是：你能解释清楚排列吗？

先预测：

四张不同卡片排成一列，为什么是乘法而不是加法？
从五张卡片选两张时，20种排列为什么只对应10种组合？
帕斯卡三角形的一行为什么恰好把全部n比特模式分成若干组？
33比特与34比特只差一位，能表示的编号却多出多少？

3.1 排列

3.1.1 书店

书店里的数学从人物关系继续。尤里戴着棒球帽，栗色辫子垂在帽后；她仍记得上一章突然问出的“哥哥被亲过吗”，也仍会把“鲡鱼与绿鲤鱼”说成绕口令。她真正想弄懂的，是把四张不同卡片A、B、C、D排成一列共有多少种方法，也就是问题。

强调顺序。ABCD与BACD选择了同样四张卡片，但第一位不同，所以是两个排列。

3.1.2 豁然开朗

计数的基本要求是。上一章把骰子平局漏掉，就是遗漏；若同一无序选择被不同书写顺序反复计算，就是重复。

仅仅说“认真数”不能保证正确。原章给出的战术是：先用具体对象建立结构，再顺着结构计数。树形图让每个完整排列对应一条从根到叶的路径，因此可以检查是否每个选择都被覆盖，而且每条路径只落到一个结果。

3.1.3 具体示例

四张卡片依次放入四个位置：

第一位有4种选择；
第一位确定后，对应每一种情况，第二位有3种选择；
前两位确定后，对应每一条已有路径，第三位有2种选择；
最后一张卡片只有1种选择。

把选择过程分成四层。叶子数为：

4\cdot3\cdot2\cdot1=24.

乘法来自每一层都对上一层的每条路径重复发生。

这里的乘法来自“对应每一根树枝”：已有4条分支，每条再长出3条，共有4×3=12条；每条又长出2条，变成24条。最后乘1看似没有分杈，却让逐层规律保持完整。

3.1.4 找规律

分支数按：

4\longrightarrow3\longrightarrow2\longrightarrow1

逐次减少。树形图不是为了把24个答案画得更花哨，而是让可见。

若第一步有a种选择，并且对应每一种第一步结果，第二步都有b种选择，则两步完整结果数是ab。这里“对应每一种”是的语言信号；如果两个分支互斥、只选其中一类，才使用加法。

3.1.5 一般化

把4替换成任意正整数n：

n,\ n-1,\ n-2,\ldots,2,1.

定义：

n!=n(n-1)(n-2)\cdots2\cdot1.

所以n个不同对象全部排成一列共有：

n!

种。小阶乘表为：

$n$	1	2	3	4	5	6	7	8	9	10
$n!$	1	2	6	24	120	720	5040	40320	362880	3628800

看到3628800时能认出10!很方便，但公式的来源比背表更重要。

3.1.6 铺就道路

原章把学习方法压成一条道路，也就是具体示例→找规律→一般化：

\text{具体示例} \longrightarrow \text{找规律} \longrightarrow \text{一般化}.

具体示例提供可操作经验；找规律看见结构；一般化则把“试过才知道”变成“不必枚举也能知道”。之后还要验证规律是否正确。公式不是免除思考的口令，而是把已经理解的结构压缩成可复用形式。

3.1.7 那家伙

“我”把问题换成“鲡鱼与绿鲤鱼”六个字的排列。尤里立即回答6!=720，却忽略了两个“鱼”无法区分。这个悬念留到图书室继续解决。

她也说出学习排列的真正原因：班里有个数学很厉害的男生，常出谜题，还问她能否解释排列。她想下次决一胜负，却听说“那家伙”因为家里的事情要请假一段时间。此时它只是叙事旁枝，章末才会显出重量。

3.2 组合

3.2.1 图书室

时间过去，“我”的年龄从16变成质数17，也进入高三。放学后的图书室里，泰朵拉摔散卡片，那是村木老师给的学习材料；收拾起来的内容正是排列与组合。数学从书店楼顶换到图书室，具体例子也从“全部排放”扩展到“从n个对象中取k个”。

3.2.2 排列

从n个不同元素中有顺序地取出k个，第一位有n种，第二位有n-1种，直到第k位有n-k+1种：

P(n,k) =n(n-1)\cdots(n-k+1).

要写成阶乘，只需观察：

n! = \underbrace{n(n-1)\cdots(n-k+1)}_{\text{前k个因子}} \underbrace{(n-k)\cdots2\cdot1}_{(n-k)!}.

把未使用的切掉：

P(n,k)=\frac{n!}{(n-k)!}.

例如从5个对象有序取2个：

P(5,2)=5\cdot4=\frac{5!}{3!}=20.

也就是P(5,2)=20。分数一定约成整数，因为它本来就是前k个连续整数的乘积；分母只是把人为补齐的尾巴移除。

3.2.3 组合

忽略内部顺序。五张卡片选两张时，有序结果AB与BA在排列中不同，在组合中却代表同一对。

每个k元素集合内部有k!种排列，因此有序取出的P(n,k)个结果把每个组合重复计算了k!次。除去重复：

\binom nk =\frac{P(n,k)}{k!} =\frac{n!}{k!(n-k)!}.

例如：

\binom52 =\frac{20}{2!} =10.

公式中的除法不是“恰好能约分”，而是把同一个无序对象的重复书写全部折叠。必为整数，因为计数对象本身保证结果为整数。

组合数不是凭空出现的除法，而是把每个无序对象的内部顺序折叠。

3.2.4 鲡鱼与绿鲤鱼

先假装两个“鱼”可区分，六个位置有6!种排列；去掉标签后，交换两个“鱼”不会产生新文字序列，所以每个真实结果被数了2!次。这就是相同文字的排列：

\frac{6!}{2!} =\frac{720}{2} =360.

更一般地，若n个对象中各类重复数为r_1,r_2,\ldots,r_m，不同排列数是：

\frac{n!}{r_1!r_2!\cdots r_m!}.

3.2.5 二项式定理

为：

(a+b)^n =\sum_{k=0}^{n} \binom nk a^{n-k}b^k.

变量太多时，原章建议做一般化的逆操作：。

完全平方公式是：

(a+b)^2=a^2+2ab+b^2,

(a+b)^3=a^3+3a^2b+3ab^2+b^3.

为什么系数是组合数？展开n个因式时，每个因式都要选择a或b。要得到 $a^{n-k}b^k$ ，必须从n个因式中选出恰好k个提供b，选择方法正是：

\binom nk.

代数系数因此具有直接的计数意义。

3.3 (2^n) 的分配

3.3.1 帕斯卡三角形

米尔嘉在柑橘香中出现，把二项展开的系数认作，也就是杨辉三角形：

n=0              1
n=1            1   1
n=2          1   2   1
n=3        1   3   3   1
n=4      1   4   6   4   1
n=5    1   5  10  10   5   1

内部递推为：

\binom nk = \binom{n-1}{k-1} + \binom{n-1}{k}, \qquad 0\lt k\lt n.

它不是纯代数巧合。固定一个元素A，从n个元素选k个的结果分成互斥两类：

选择A，还要从其余n-1个选k-1个；
不选择A，要从其余n-1个选k个。

两类不重叠且覆盖全部结果，所以用加法合并。帕斯卡三角形的“相邻两数相加”正是一次分情况讨论。

3.3.2 位模式

一个比特有0、1两种状态，n比特共有：

2^n

种。五比特共有32种，从00000到11111。按其中1的个数k分类：

1的个数 $k$	0	1	2	3	4	5
模式数	1	5	10	10	5	1

“恰有k位为1”等价于“从n个位置选择k个放1”，所以第k组大小是：

\binom nk.

把所有组相加：

\sum_{k=0}^{n}\binom nk=2^n.

也可以在二项式定理中令a=b=1：

(1+1)^n =\sum_{k=0}^{n}\binom nk =2^n.

于是二项式、帕斯卡三角形和位模式分类不是三件偶然相似的事，而是同一组合结构的代数、递推与编码表示。标题“(2^n)的分配”指的正是：全部2^n个模式按1的个数分配到各个组合数组中。

同一组组合数既是二项式系数，也是恰有 k 个1的比特模式数量。

3.3.3 指数爆炸

来自每增加1比特就把状态空间翻倍：

2^{n+1}=2\cdot2^n.

若要给100亿人分配不同编号，需要最小的b满足：

2^b\ge10\,000\,000\,000.

计算相邻幂：

2^{33}=8\,589\,934\,592,

2^{34}=17\,179\,869\,184.

因此：

2^{33} \lt10\,000\,000\,000 \lt2^{34},

33比特不够，最少34比特。标题数字就是34次二分之后的叶子数。泰朵拉从“至少一万比特”一路猜到300比特，真实答案却只有34，显示人类直觉多么容易低估指数。

一位的差别把容量从不足目标推到足够目标，因为每加一位容量翻倍。

原章继续把尺度推向宇宙：地球原子数约为2^170，银河系原子数约为2^223，宇宙体积约为2^280 cm³。若每个立方厘米分配一个编号，280比特已经能在这个模型中定位全宇宙的一格。

3.4 幂运算的孤独

3.4.1 回家路上

回家路上，“我”在脑中看见34层树形图：34次分杈产生17179869184个叶子，足以给全球100亿人逐一编号。每个人都像无数过去岔路最终抵达的一片叶子；能区分所有人，也意味着每个编号只能落在一个位置。

指数在数学上制造充足空间，却同时放大了“我们只是众多可能之一”的感受。数字从技术容量转成了标题中的孤独。

3.4.2 家

到家后，母亲低声说尤里来了。她独自坐在房间里，马尾辫无力垂下，终于说出：“那家伙要转校了。”原来那个常和她互出数学谜题、谈书、学习、吵架又和好的同班男生，将要去远方，不能再参与她的每一天。

前面轻松的排列问题至此闭合。两个人原本共享许多路径，只需一次“去”或“不去”的1比特差异，道路就会越走越远。每天充满分岔，树形图能数清叶子，却不能替人选择，也不能把离开的分支折回。

“我”找不到能消除心酸的话，只能靠近那片由280比特定位的空间，把手轻轻放在尤里头上。章首借《鲁滨逊漂流记》谈编筐手艺和陪伴，章末则让组合结构与人的关系缠在一起：数学让分岔变得可见，而陪伴让其中一条路径不再只是编号。

官方概念回收：从计数结构到编码边界

官方概念锚点补全：标题的 2的34次方等于17179869184，也写作 2^34=17 179 869 184；周六尤里在新开的书店和书店楼顶遮住我的眼睛。四张不同卡片A、B、C、D 的顺序不同会产生不同排列，完整计数为 4×3×2×1=24。每一层都对已有路径展开，所以使用乘法原理；两个分支互斥才使用加法。阶乘还约定 0!=1，n个不同对象全部排成一列有 n! 种。

重复元素部分：鲡鱼与绿鲤鱼中两个鱼无法区分，因此交换同类只算一次；从n个对象中取k个时，排列公式中的阶乘尾巴会被切掉。组合忽略顺序，AB与BA视为同一项，每个无序选择有 k!种排列。二项式定理也可以通过赋值进行特殊化；展开时每个因式都要选择a或b，帕斯卡三角形边界为1，上一行相邻两项相加，递推分为选择A和不选择A两类。

编码部分：2的n次方的分配就是 2^n的分配；五比特的位模式覆盖 00000到11111，按1的个数分类后得到 1、5、10、10、5、1，其中恰有k位为1等价于从n个位置选择k个放1。因此所有组合数之和为2^n，正好对应令a=b=1。指数增长还可用尺度感理解：地球原子数约为2^170、银河系原子数约为2^223、宇宙体积约为2^280 cm³。

分步1 / 4

1. 树：按路径计排列

从四张卡片开始，逐层固定位置；每条根到叶路径对应一个排列，叶子数是 4×3×2×1=24。