从标数法求最短路径数到杨辉三角的思考_杨辉三角与路径问题

上周旁听了一节小小的学而思数学网课，写一篇心得。一直想写的，但工作日一直都在忙，今天终于有所闲暇，就坐下来写点吧。

上周日，我蹲在边上写代码，小小把电脑搬到餐桌上学而思网课，我侧耳被一道题目吸引了。

题目是这样的：

…
作为一个受过高等教育的人去解这道题，会怎么做？先仔细想一下。

我自己的思路这样子的：

从A走到B的动作，我分为5个步，即向右，向右，向右，向上，向上。但是也可以换个顺序，所以我只需要在5个步骤里任意选3个向右就是路径的总数量了， 即

C

5

3

C_5^3

C53​

我会解这道题那完全是因为我懂排列组合的概念并且记得排列组合的公式，仅此而已。换句话说，拿到题后，我并没有进行除了我该用哪个数学公式之外的任何思考，简单点说，我没有进行思考。

如果我从来没有学过排列组合呢？我该怎么办？说实话，要是不知道排列组合公式，我估计不会这道题…真的，我真的不会，当然，给我点时间，我应该能找到方法，或许，我应该能自行推导出排列组合公式。

所以我更想知道一个不懂排列组合公式的人是怎么想的。

我老婆(她曾经会排列组合公式的，只是忘了)的方法是一条一条路数，而小小则托着下巴直接说不会…

真实情况就是这样，如果不说这是一道数学题，大多数人的做法就是要么一条条数，要么就干脆放弃。但因为这是一道数学题，是题就要解，所以大多数人会去有意地将它归为某一类问题，然后用公式去解。

学而思网课的老师教的是标数法，简易展示如下：

本文不是讲标数法的，本文只是路过而已，详细的过程还请自行百度。

说实话，我小学从来都没有听说过这个标数法，甚至中学，大学都没有听说过，我觉得这个方法要是自己想出来的，那是相当牛X了，我并不觉得教这个东西的老师有多牛X，因为老师也是从别的地方看的，这个方法相当简单，是个人一看就懂…

往后，如果再碰到类似的题目，那就可以用这个标数法了，这个方法老师一讲，马上就成了新的 公式 ，基于这个新公式的应用，就出来了很多稀奇古怪的新题目，但不外乎：

• 把四四方方的矩形搞成不规则的。
• 不再是矩形，换成多边形。
• …

然后可以通过套用标数法把这些看上去很麻烦的题目解出来的孩子，那就是好学生，但事实上，他们可能只是记住了公式而已。

形而上的思考暂且先到这里，现在，我们抛开题目本身，看看它背后有什么好玩的，继续我的故事。

网课结束后，我老婆和小小准备关电脑吃午饭，我说，等一下，这么好玩的东西，难道不想再瞄两眼吗？我得看看这里面有什么规律。

头稍微一歪，马上看出这就是杨辉三角。

事实上，在计算的过程中，你可能已经注意到标数法和杨辉三角的关联了：

• 标数法一个节点的标数等于它左边节点标数和下面节点标数之和。

这正是杨辉三角生成的规则：

• 第$n$

此外，就算使用排列组合公式，

C

m

n

C_m^n

Cmn​也是这个意思。

可是遗憾的是，百度谷歌“标数法 杨辉三角 二项式系数”结果寥寥，很少有人把这些关联起来。

管它呢，让我们继续看这个标数法节点标数或者说是杨辉三角数的生成规则，以

1

,

2

,

1

1,2,1

1,2,1为例：

这没什么大不了的，本来就是这样生成的，然而，我们把 “左边+右边” 换个写法，就相当好玩了，换成什么呢？请看下图：

这是什么？这是加法竖式啊！

这个加法竖式怎么来的呢？考虑到一个加数是另一个加数左移1位得到，很显然，这是第一个加数乘以11的中间步骤啊：

这样我们可以得到的性质是：

• 杨辉三角每一行的数字拼起来是上一行数字拼起来乘以11的结果。

考虑到杨辉三角从1开始生成，所以：

• 杨辉三角每一行数字拼接都是11的次幂。

通过这么一个自发的推算过程是不是比老师直接告诉你这个性质好一点呢？

让我们继续。

上面提到杨辉三角每一行能拼接成一个11的次幂的数字，比如1331就是11的3次幂，那么从1，5，10，10，5，1开始如何拼接呢？就以1，5，10，10，5，1为例，显然直接拼接的结果15101051是不对的。

其实，在进行竖式计算的时候，我们一直都投了个懒，这个老师都没有告诉过我们。那就是关于进位的。

标准的计算姿势是：

1. 分别算出个位$x_1$
2. 求结果$r=x_1+10\times x_2+100\times x_3+1000\times x_4+$

然而，我们在计算的过程中就已经进位了，而不是在最后统一处理进位。我们从小学开始学竖式的时候，一开始老师就教我们直接进位的，所以，当我们看到20个10这种说法时，总感觉怪怪的，我们喜欢听到的是2个100。

我们来用标准的方式计算一下1，5，10，10，5，1的拼接。它的上一行是14641，它是11的4次方，我们试试14641乘以11的竖式：

最后的结果是161051，而它正是11的5次方！

进一步，1，5，10，10，5，1继续下一行就是1，6，15，20，15，6，1，它按照十进制拼接就是

r

=

1

+

6

×

10

+

15

×

100

+

20

×

1000

+

15

×

10000

+

6

×

100000

+

1

×

1000000

r=1+6\times 10+15\times 100+20\times 1000+15\times 10000+6\times 100000+1\times 1000000

r=1+6×10+15×100+20×1000+15×10000+6×100000+1×1000000
由此，就找到了将一个杨辉三角行转换为十进制数的方法，这可是自发找到的哦。

可是反过来呢，如果有人告诉你2357947691是11的9次方(它确实是)，然后问你，它如何展开成杨辉三角行？

你可能会说，这还不简单吗？请看：

(

10

+

1

)

9

=

C

9

0

×

10

+

C

9

1

×

10...

(10+1)^9=C_9^0\times 10+C_9^1\times 10...

(10+1)9=C90​×10+C91​×10...
然后取10的系数就好了…

当然，这是正确的，但是却根本不好玩。好玩的方法如下：

一个看上去很普通的数字，2357947691，你从它的长相上根本就看不出它和杨辉三角有什么关系，但是经过上述这么一番折腾，隐藏的东西便显露了出来，这个过程纯粹就是一个数字游戏，没有套用任何公式，给人的感觉就是，一个藏得很深的东西被扒拉了出来…

…

后面还有很多好玩的东西，时间有限，我仅再举一例。

我们注意，杨辉三角的第一行是一个1，然后第二行展开成1，1，我们把每一行的数字相加，第一行的和显然就是1，第二行显然是2。这没什么好说的。

通过上面的竖式生成规则，我们发现，下一行其实就是上一行左移一位和其本身相加的结果。加法是符合交换律的啊，所以我们发现如果每行求和，这里面就有两个加法的过程：

1. 平行横着加-行求和
2. 移位竖着加-求下一行

按照统一进位原则，在计算过程中是不进位的，所以每一行的数字求和，其实就等于2的上一行的求和：

Σ

A

n

,

i

=

2

×

Σ

A

n

−

1

,

i

\Sigma A_{n,i}=2\times \Sigma A_{n-1,i}

ΣAn,i​=2×ΣAn−1,i​

哈哈，还用记忆背诵那些杨辉三角的性质吗…

第

n

n

n行数字的和是2的

n

−

1

n-1

n−1的2倍，于是行求和序列就是：

1

,

2

,

4

,

8

,

16

,

32

,

64...

1,2,4,8,16,32,64...

1,2,4,8,16,32,64...

2

0

,

2

1

,

2

2

,

2

3

,

2

5

,

2

6

.

.

.

,

2

n

−

1

2^0,2^1,2^2,2^3,2^5,2^6...,2^{n-1}

20,21,22,23,25,26...,2n−1

…
再次扯到我自己的一点形而上的认识。

说实话，我真的不会这道题，我之所以能在5秒内解答，是因为我无非把排列组合公式记住了而已…

在我写这篇文章的同时，小小在练习钢琴，小小的钢琴老师希望在弹奏之前要有自己的思考，不然只要有谱子，苦练，谁都是可以弹奏的…这和我的想法不谋而合，他只是记住了谱子而已…

重要的是独立思考，而不是去记忆一些范式然后去搞一些奇技淫巧。

我们的奥数班牛X不，秒杀美国啊，原因真的是我们比美国人聪明吗？我觉得不，我一向都觉得中国人和欧美人都是一样的，谁也不比谁更优秀，我们之所以奥数牛X完全是因为我们记住了更多的公式和更多的解题技巧而已。

以上述我的分析为例，如果要求2357947691的分解式，我估计真的会折腾一番，然而根本没有必要，照着公式求

(

10

+

1

)

9

(10+1)^9

(10+1)9的系数即可…

我们在小学中学学了太多的解题技巧，碰到什么题目用哪个技巧，所需的只是记忆力而已。到了大学，当我们接触微积分的时候，发现学习微积分并不需要中学的数学基础积累，甚至更简单，依然还是那么一堆的公式，依然只是需要记忆力即可…

如果说能把微积分教程的附录习题做对就能获得腾讯阿里的offer拿百万年薪，我觉得任何一个文科生都能做到，所需的不过只是记忆力而已。

我是觉得我老婆作为一个日语专业的文科生是完全可以完成微积分的学习的。而且我跟同事还夸下海口，我准备试试让小小在小学期间学会微积分，无非记忆几个公式和解题流程而已嘛，我没有看出这个和四则混合运算有什么本质的区别。

当然了，如果真的要理解微积分的本质，那估计真的要花费好久好久。我自己这么做了，却连本科都没有考上，也是唏嘘。我反省过，自己花了太多时间在一个公式的背后，而不是这个公式本身，并且令人遗憾的是，我没有记住它…

但是推演让人快乐。

知乎上看到过一篇关于小学，中学，大学数学的关系的超好回答，分享一下。

我们眼里，它们的关系是这样的：

但实际上，它们却是这样的：

说实话，我上周真的被这个学而思的标数法震撼到了，它是多么美的一个step by step的算法，计算机的所有逻辑都是这么完的啊！

你看看加法器的电路实现，再对比一下加法竖式，简直是一模一样，这意味着什么？

计算机是人脑的模拟还是人脑的超越？到底如何实现AI？如何让计算机理解韦达定理…

这意味着什么？我来讲，一缕月光照当头，上下光而相凑，鸡屎也不流，用手殴，净肉球。

浙江温州皮鞋湿，下雨进水不会胖。