用“双射”的思想解决排列组合问题

“双射”（bijective）其实是个比较土味的数学名词，因为在关系代数中我们更喜欢称它为“一一映射”。关系代数是研究集合之间“映射关系”的数学分支，然后集合的概念抽象到别的学科上就产生了各种细分理论，上一篇《VLQ偏移自然数》也是围绕“双射”这个主题展开的，即编码与自然数一一映射。

其实在高中数学“排列组合”中就已经介绍了各种“双射”的思想来解决实际问题，比如有100个球队，两两进行淘汰赛，最后产生一名冠军队，请问要进行多少场比赛（无平局）？

按照常规思路，应该这样分析：

1. 第一轮要进 行 50 场 比赛 , 留下50 队 ;
2. 第 二轮 要进 行 25 场 比 赛 , 留下 25 队 ；
3. 第三轮 要进 行 12 场 比 赛 , 留下 13 队 ;
4. 第四 轮 要进 行 6 场比赛 , 留下 7 队 ；
5. 第五 轮要进 行 3 场 比赛 , 留下 4 队 ；
6. 第六轮 要进 行 2 场 比赛 , 留下 2 队 ;
7. 第七轮 是 一场决 赛 , 产生一 名冠 军 队；

因此总共进行了50 + 25 + 12 + 6 + 3 + 2 + 1 = 99 场 比赛。

我相信，当看到“99”这个答案，你会意识到一定有更简单的算法。。我们换个思路分析一下，每进行一场比赛一定淘汰掉一个队：【一场比赛】和【淘汰一个队】一一对应，那想要淘汰掉99个队有且只有进行99场比赛。这种算法立即得到答案，比前面的“直觉式迭代”简便得多，这道题类似于“空瓶换水问题”：好像是2个空瓶可以换1瓶水，然后问能买多少水来着，解题思路都是通过一一映射转换问题，避免尝试性解题。

排列组合公式

我们再看一道题：把 7 本 不 同的书 , 分给 甲 2 本 , 乙 1 本 , 丙 4 本 , 问有多少种 分 法?

这里再介绍一种解题习惯：分而治之，即把大问题拆分为可以独立考虑的不同阶段，本题中，可以先把乙和丙看成整体，问题变成：7本书分甲2本，其他人5本，有多少种分法？这样直接调用无序组合数公式即可：C(7,2)=21种。

组合数公式是指从n个不同元素中，任取m(m≤n)个元素并成无序的一组，求得组合的总数量。

组合数公式：

在以上的21种分法中，无论剩下的5本书如何分配给乙和丙，都不影响已经分给甲的书，所以这21种情况是对称的。然后分而治之的子问题就成了：把5本不同的书分给乙1本，分给丙4本，总共是C(5,1)=5本。再把问题整合起来，7本书分给甲乙丙2、1、4本共C(7,2)*C(5,1)=21*5=105种分法。

上面我们介绍了排列组合公式、分而治之和一一映射的技巧，下面综合这些方法挑战更难的问题。

数学建模

某城有 7 条 南北街 , 5 条东西街，共4*6=24个街区，某人 要从城 的西南角走 到东北角 , 问最短的 走法 有几种?

街区：以四条街道为边围成的区域。

此题有多种解法，但使用一一映射的思想来建模是最简单的，首先我们把问题转换成上面这个坐标系，从O点走到A点的最短路径有多少条，这一看就是道排列组合题，我们设每走过一个街区消耗1步，向右走记作x，向上走记作y。

无论怎么走，总要向x轴方向走6步，向y轴方向走4步，总共走10步，但x和y出现的顺序可以是任意的比如xxxyyyyxxx，每一种组合和一条最短路径一一映射，设一个长度为10的数组，数组中任取4个位置设为x，剩下的为y，总数量就是C(10,4)=210种。

“ 一一对应” 解题思路的关键是 建立 怎样 的 “ 对应” 关 系 , 才 能方便 地达 到 解题 目的，这 是 一个技 巧 问题。

高中数学老师留给我映像最深刻的一句话是：数学应该越学越简单，因为你掌握的方法越来越多了。这句话真的是god damn right。

严格递增数列

本期分享一共4道初等排列组合问题，难度依次递增，下面利用之前所学的所有技巧挑战最后一道题：

我们都知道在1，2，3，...，n这n个元素的数列中任取r个元素【无重复，r≤n】可以取到C(n,r)种不同的组合，也就是上面的组合数公式。那如果允许重复选取，比如全选1【r可以大于n】，有多少种组合？

解：

和排列数不同，组合数没有顺序（顺序没有意义），也就是说我们可以给它们强行排序。我们取一组实例：X1 ≤ X2 ≤ ... ≤ Xr，这是一组递增数列。

下面，我们要把递增数列映射到严格递增数列，就是想办法把所有“≤”变成“<”。为啥？因为严格递增数列可以直接套用组合数公式呀！

我们从X1到Xr，分别加上0，1，2，...，r-1，得到Y1 < Y2 < ... <Yr，如下图：

我们成功地把递增的X数列一一映射成了严格递增的数列Y，现在只要统计数列Y的数量就是数列X的数量。显然【万恶的显然成立】每一个Y都不重复，而Yr ≤ n+r-1，此时的情况相当于从1，2，3，...，n+r-1中任取r个不重复的元素（每个元素只能选1次），可想而知，答案是C(n+r-1, r)。

从小学到大学，从初等数学到高等数学，考试成绩总是两极分化，其根本原因在于：几乎每道题都有捷径可走。如果观察过考试题的答案就会发现，答案的形式总是异常简单，都是简短的表达式和数字，老师也不喜欢结果复杂的题目：即使题目很复杂，“解”总是很精简。

于是有了一种逆向思维：既然已知结果的形式很简单，那一定有简单的算法。而“一一映射”就是这种数学捷径之一：通过将原始问题映射到更简单的模型。而这种映射总是能找到，在争分夺秒考场上敢于“冒险”花时间寻找这种映射的学生成了学霸。这就是数学考试两极分化的原因。

<完>