几个不尽相异元素全排列在棋盘最短路线上的应用

王鸿飞

摘要：提出了正方形多道纵横线相交图形A →B最短路径的几种方案。经证明，利用杨辉三角形是

      解决最短路径的最简便方法。对城市街区交通走向具有一定实际意义。

关键词：最短路径  杨辉三角形

一、  棋盘上的最短路径

围棋盘呈正方形，纵横各19道线，如果从棋盘一个角的一个顶点出发，沿着格子线，到对角顶点，问有多少种不同的最短路线？可以用最原始的方法，沿着格子线，把不同的最短路线数出来，但是不多久就会发现，如此下去重复和遗漏在所难免，而且巨大的天文数简直令人在有生之年无法数尽。

二、  标记法

为了问题的解决，我们把棋盘缩小一些如图（一）。问从A到B有几种最短路线？我们不妨把从A到各个交叉点的最短路线的种数记录下来。例，从A到a₁有1种走法，从A到a₂也有1种走法，各记1。到a₃点，必须经过a₁和a₂，所以从A到a₃和种数为1＋1＝2种，在a₃点处记上2。再看a_6，从A到a₆必须经过a_3、a₄点，所以a₆上的数字记号应为a_3、a₄上数字记号之和，为2+1=3，把3记在a₆位置上。用这样的方法到把从A点到任何一点的走法的种数计算出来，我们称为标记法。

（图一）  （图二）

三、  杨辉三角形

    把棋盘放大，如图（二），可以发现，沿着斜线的各组数字，恰好是二项式系数的排列，整个图形可以称之为杨辉三角形，这样我们在计算从某点到其它任一点最短路线时就可以不借助于标记法，而可以套用代数公式了。

例：从A到M有多少种最短路线？

解：M处在第5道斜线上，所以，有n=5、记B为第一项，M处在第4项则r=4。所以M项应为。

（插入公式）

四、  几个不尽相异元素的全排列

上面的发现似乎有点意外，是否还有一种更严谨的数学意义上的计

算法则呢？先看下面例题。

例：有大小相等的颜色弹子4粒，其中3粒是红的1粒是白的，摆

成一排，问有多少种不同的排法？

解：设所求的方法有N种每一种排列中都有红色3粒，白色1粒，

例如其中之一为。

      （红）  （红）  （白）  （红）

若把3个红色弹子，换为黄、绿、黑3粒不同颜色的，则对应上面的一种排列就有下面。

（黄）（绿）（白）（黑）

（黄）（黑）（白）（绿）

（绿）（黄）（白）（黑）

（绿）（黑）（白）（黄）

（黑）（黄）（白）（绿）

（黑）（绿）（白）（黄）

所示：P₃＝3！＝6种排列

而4粒颜色不同的弹子排列种数为4！应该等于4粒弹子其中有3粒颜色相同的排列种数N的3！倍，也就是，N·3！＝4！由此得到所求方法数：

（插入公式）

一般地，若几个元素里有P个元素相同，又有q个元素相同，、、、又有r个元素相同（p+q+、、、＋r＝n），全取其几个元素所进行的排列，叫做几个不尽相异元素的n元排列，或n个不尽相异元素的全排列。

设N为所有不同的排列方法数，若把其中P个相同元素看成是P个各不相同的元素，那就有N·P！种排列法，若再把其中q个相同元素看成是q个各不相同的元素，那就有N·P! ·q!种排列法；再把其中r个相同元素看成是r个各不相同的元素，那就有N·P! ·q! ·…..r!种排列法。而种数N·P! ·q! ·…..r!就是等于几个相异元素所成的全排列种数n!即：

N·P! ·q! ·…..r!＝n!

因此得

        （插入公式）

这就是n元，不尽相异元素的全排列种数公式。

例：某区有南北街道7条，东西街道5条，汽车从区的西南角A驶往东北角B，最短的不同路线有多少种？

解：每条东西向的街被分成6段，每段用a表示，南北被分成4段，每段用b表示。汽车的最短路线任一种必须含有6个a和4个b，例：aabaabbaab，所对应的路线（如图三）箭头所示路线。

（图三）

这里n＝10， P＝6、，q＝4

因此所求最短路线种数为

   （插入公式）

例：有3本相同的哲学书，4本相同的美术书，5  本相同的数学书，放成一排，问有多少种放置法？

解：P＝3， q＝4， r＝5， N＝P+q+r＝12

所以种数：（插入公式）

现在可以回到围棋盘上，我们记棋盘的横一格为a，纵一格为b，从棋盘的一个顶点A到另一个对角点B，任一条最短路线，必须也只能走18个a和18个b，这样实际上是一个2类不尽相异元素P＝18，q＝18，n＝36的一个全排列。

答案应为：

               （插入公式）      

这是严格数学意义上的一种思考计算方法。

Mathematics in everyday life --- how to determine the shortest route in urban areas

Wang Hongfei

Abstracts: This paper makes known several choices to determine the shortest distance between A and B, both being points of intersection in a square having some longitudinal and transverse lines within. It proves that with the help of mathematics, it is possible to find the shortest route easily. This paper therefore throws some light on the reasonable direction of traffic I urban areas.

Key words: the shortest route; Yanghui triangle