组合数学之方格路径

一个简单的问题

问从一个横边长为m，竖边长为n方格棋盘的一个角走到对角点的最短路径共有多少种方法？这个问题应该会有很多人见到过，想明白的话这也是一个很简单的问题，但是如果在这个问题上进行一点小小的改变，这个问题也是可以很有意思的。

level 0

方便起见就不失一般性的假设棋盘大小是4*3：

那么问题就是从左下角到右上角的路经数目有多少？
一种思路就是用动态规划的思想，到格子（i，j）处的只有两种方法：从（i-1，j）向右走一步或者从（i，j-1）处向上走一步。用N（i，j）表示从起点到（i，j）的路径数，则：

N（i，j）=N（i-1，j）+N（i，j-1）

所以这个3*4的棋盘问题可解：

但是说的高大上是动态规划算法，说的不好听了不就是傻算嘛……换一个角度考虑就能转化成一个高中就能瞬间写出答案的问题，其实就是一种选择的问题。因为在每个路口都要做出选择，是向上还是向右走。就好像我高中骑车上学一样。假设我家在左下角（0，0），学校在右上角（4，3）。那么我可以先向右骑一段路，到路口（1，0），我可以选择向东直行到（2，0）或者左拐到（1， 1）处，每一个路口都要做出选择，但是全程我必须也只能向北走三段路，同理向东走四段路，即在全程长为7的路程中选择三段路向北走，四段路向东走。
例如（U U R U R R R ）或者（R U R U R U R）或者（R R R R U U U）都是可能的路径。（U表示向上走，R表示向右走）。
所以总路程数就是：

C(7,3) = C(7,4) = 35

同理从（0，0）点走到（m，n）处的路线数就是C（m+n，n）或者C（m+n，m）。

level 1

好！小棋盘升级了！现在我们的问题改变了，在一个mm正方形棋盘上从角点（0，0）走到对角线上的最短路线有多少种？

升了一级也没感觉怎么样嘛！每一个路口有2种向上向右两种走法，走m步，共$2^m$种路线。就拿这个99的图来说，答案就是$2^9$呗！so easy！我想说的是，除了这一个思路，用level 0的想法解这道题。
从上往下，到达第一个点的路径数目是C（9，0），到达第二个点的路径数目是C（9，1），依次类推，到达第i个点的路径数目是C（9，i-1），这里 i 的取值区间是大于等于0，小于等于9。也就是说，总共的路径数是：

$\sum_{i=0}^9C(9,i)$

这十个值分别是1,9,36,84,126,126,84,36,9,1，而如果把这个计算过程写下来的话，我们会发现这不就是杨辉三角嘛！

—（图片来自百度，侵删）—

杨辉三角形可以用来解释二项式定理：

$(u+r)^m=u^m+C(m,1)u^{m-1}r+C(m,2)u^{m-2}r^2+……+r^m$

这里没有通常的x和y而是用u和r来表示，是因为在这里u表示向上走，r表示向右走。$u^kr^{m-k}$的项表示共走m步，其中向上走了k步，其余时候向右走。而项前面的系数表示这种走法共有多少种可能性，在上式中将m=9带入，就是我们上述的解。令u=r=1，整个式子的和为512。
杨辉三角又名Pascal三角形，还有很多有趣的性质，比如和斐波那契数列的联系，与题无关不赘述。

level 2

前面上了两个战五渣热身，现在大家是不是觉得战斗力满满，想打十个！接下来的就是精英棋盘了！现在的棋盘变成了这个样子：

在这个9*9的棋盘中我们从起点走到终点，限制是不允许走红色的区间内，也就是说可以是走在起点到终点的连线上的。老司机一看可能就知道：啊！好办！这不就是卡塔兰数嘛！直接上公式啊：

$C_n=C(2n,n)/(n+1)$

直接带入n=9计算得到Cn为4862！bingo！回答正确！但是一是可能很多童鞋不知道catalan数或者没想到可以使用catalan数，另一方面，假设题目要求稍作变动，Catalan数也不能简单的解决这个问题了比如下例。

level 2 Plus

这个棋盘发现自己可以直接被公式解决很不开心，于是把终点挪了挪，现在就不能直接套用Catalan数了。题目要求还和之前一样，不许走到红色区域内部，求最短路径数有多少？
我们可以考虑，这道题要求我们从（0，0）处走到（9，6）处。而第一步我们只能向右走到（1，0）位置。所以从（0，0）点出发到重点的线路数目和从（1，0）点出发的线路数目是一样的。而且，从（1，0）点出发到终点的所有最短线路中，有进入红色区域和不进入红色区域两种路线。那么这道题的就变成了求解从（1，0）点出发的到达终点的所有路线减去从（1，0）点出发的途径红色区域内部到达终点的路线。但是这么看的话，问题不但没有变得简单，反而需要求的量更多了。
然而从（1，0）点出发的所有路线我们是可以通过level 0的结论立刻得知的。那经过红色区域的路线数目呢？

我们的要求是不能进入红色区域内部，也就是说红色细线上面的点可以经过，而红色粗线上面的点是不允许碰的。而我们只要求出所有S点到终点的路径中与红色粗线相交的数目就可以了。
可以进行这样的转化，每一条S到终点与红色粗线相交的路线都可以转化为T到终点的一条路线。转化方式就是设P是路径与红色粗线相交的第一个点。把S-P的一段路线关于红色粗线进行轴对称到T-P即可。一旦有了这种一一对应关系，我们也就如下计算：
Ans = 起点到终点不进入红色区域的路径数
= S点到终点不进入红色区域的路径数
= S点到终点所有路径数 - S点到终点与红色粗线相交的路径数
= S到终点路径数 - T到终点路径数
= C（14，6）- C（14，4）
= 2002
由于这是level 2 plus的解法，当然去搞level 2也是so easy。用这种方法去解level 2的话：C（17，8）- C（17，7）= 24310 - 19448 = 4862。

插播一条来自Catalan的紧急新闻

Catalan数实际是一种非常有趣也变化多端的递推序列，这里不详细地讲他的公式了。有很多种形式的题目实际都是Catalan公式的变形应用，这里只给出我印象深刻的一个例子，是我在考研复习时看到的。说一个长为n的字符串和一个栈，整个字符串经过出栈入栈可以有多少种字符串。
比如：abc这个字符串，经过（入入入出出出）的堆栈处理顺序得到cba，若是经过（入出入出入出）得到abc……
总的可能性就是卡塔兰数，实际上这个（入出…….）这个序列可以转化为在棋盘途中的（上右……）的一个路径，所以可以相互转化。
网上还有很多例子，什么卖票呀，加括号啊。殊途同归。

level 3

俗话说得好，流水的学生，铁打的题型。（敢问这是哪里的俗话。。。）打倒了一个棋盘，还会有千千万万个棋盘站起来！

又回到最初的起点，又是那个9*9的方格棋盘。不过岁月是把杀猪刀，让咱走了这么多遍，棋盘也受不了，现在L1、L2和L3几段路路面维修，禁止通行，那么现在问从起点到终点有多少种最短路径啊？
最短路径啊？
短路径啊？
路径啊？
径啊？
啊！！！
(╯°Д°)╯︵ ┻━┻

好，诸位先把桌子捡回来，然后继续看这道题！
这道题其实仔细想想并不难呀，就是总的路径数减去经过L1的，经过L2的和经过L3的呗，有一个小陷阱是分别减的时候可能会有重复减去的部分。可以参考下面这段小学奥数题。

一个班有48人，班主任在班会上问：“谁做完语文作业？请举手！”有37人举手。又问：“谁做完数学作业？请举手！”有42人举手。最后问：“谁语文、数学作业都没有做完？”没有人举手。求这个班语文、数学作业都完成的人数。

如果大家都想起了被童年时期奥数题所支配的恐惧了，那么这道题也可以解了。所求路径数就是：总路径数 - 过L1路径数 - 过L2路径数 - 过L3路径数 + 过L1L2路径数 + 过L1L3路径数 + 过L2L3路径数 - 过L1L2L3路径数。这里不写计算过程了，我计算的答案要是没错的话是26312。

level 3 Plus

然而故事并没有就这么结束。（求求你结束吧。）我们的棋盘君知耻后勇。（我要是能像棋盘这么上进就好了。）他发现自己被小学奥数参赛选手解出来非常羞愤（太敏感了吧！），于是题目变成了这样：

诶？
是的！你没有看错！图还是那张图，但是背景故事已经变了！（噗！）现在L1，L2，L3不是修路了，而是三个麦当劳汽车餐厅，你从左下角的家去右上角的公司上班，途中要经过三个汽车餐厅的一个而且只能经过一个，比如在L1这条路上的麦当劳汽车餐厅买完东西之后就不许去L3了，因为一般这三条路上车比较多，你怕堵车。那么现在问题来了！最短路径有多少条。。。
当然了，可以计算经过L1不经过另外两个，另外两个也这么计算，然后加到一起可以求解。可是这么一点没有逼格。这里也不多说废话了，解这道题的工具是广义容斥原理。（弄了半天还是要容斥原理来解！）容斥原理解决的是几个集合的并集，也就是说有很多性质，我们可以用容斥原理求至少满足一个性质的元素数目。而广义容斥原理可求解恰好满足i个性质的元素数目。
在这就不深究原理与证明了，广义容斥原理用到两个变量：


且直接定义$\alpha(0)$ = 性质数
直接使用这个工具：
设A是经过L1的路径集合，B是经过L2的路径集合，C是经过L3的路径集合，则：

$\alpha(0)$ = C(18，9) =48620（就是总路径数，不考虑任何限制）
$\alpha(1)$ = |A|+|B|+|C| = 7056+9240+10296 = 26592
$\alpha(2)$ = |AB|+|AC|+|BC| = 1512+2772 = 4284
$\alpha(3)$ = 0

然后通过$\alpha$计算$\beta$

$\beta(0)$ = 48620-26592+4284-0 = 26312
$\beta(1)$ = 26592-2*4284 = 18024
$\beta(2)$ = 4284
$\beta(3)$ = 0

然后$\beta(i)$表示的就是恰好满足i个性质的元素数，这道题中标示的就是恰好通过i条红色路径的数目。我们想求的答案就是$\beta(1)$ = 18024.为了验证我们也可以将所有的beta加到一起就等于alpha（0），而且beta（0）的意思是不通过红色路径数，也的确是我们上一题的答案。
注：这其实是由beta的计算方法决定的，将beta纵向排开可以发现它的系数构成一个杨辉三角哦。

棋盘还有话要说

写这篇文章其实是因为最近学了一些组合数学的皮毛，感觉挺有趣也挺深奥。文章其实并没有多少自己的东西，只是把各个部分的知识点串到一起而已，写在这也只是可以起到复习的作用。数学方面我是小白，如有错误尽管拍砖。如果有时间后面会再写几篇文章。

---

参考资料：
《组合数学》（第三版） 作者：卢开澄 卢华明