如何计算相交路径的个数？

王守恩

王守恩

答案 = 1750 对。题目是从知乎过来的。后面我会给出一个笨的解法。

我特别感兴趣的是终极目标。

孤立路数量 = 总数量 - 交叉路数量

= {A-B数量}×{C-D数量} - {A-D数量}×{C-B数量}

譬如:  主帖 = {70}×{70} - {210}×{15}=1750。

当然,  A,D = 矩形,  C 在下边,  B 在上边, 且在 C,D 之间。

这是一个猜想, 会有反例吗？欢迎网友批评！谢谢各位网友！新年快乐！

倪举鹏

横坐标相同时候，AB路径的纵坐标都大于CD路径的纵坐标，程序很容易搞定

hujunhua

2#的猜想是正确的。

A↗B与C↗D的路径若相交的话，假定相交路段为E↗F，那么A↗E↗F↗B+C↗E↗F↗D=A↗E↗F↗D+C↗E↗F↗B

而A↗D与C↗B总是要相交的，假定相交路段为E↗F，那么A↗E↗F↗D+C↗E↗F↗B=A↗E↗F↗B+C↗E↗F↗D

所以A↗B与C↗D的相交路径与{A↗D}×{C↗B}是一一对应的。

题目中的图已经给出了暗示。

王守恩

我特别感兴趣的是终极目标。试试给出通项公式。

A,D = 矩形,  C 在矩形下面的边,  B 在矩形上面的边, B 在 C,D 之间。

记 A = (0,0),  C = (C,0),  B = (B,n),  D = (D,n),

孤立路数量 = 总数量 - 交叉路数量

= {A-B数量}×{C-D数量} - {A-D数量}×{C-B数量}

= \(\D\bigg(\frac{((B - 0) + n)!\ \ }{(B - 0)! n!}\bigg)\bigg(\frac{((D - C) + n)!\ \ }{(D - C)! n!}\bigg) - \bigg(\frac{((D - 0) + n)!\ \ }{(D - 0)! n!}\bigg)\bigg(\frac{((B - C) + n)!\ \ }{(B - C)! n!}\bigg)\)

在这里:  1 ≤ C ≤ D/2,  C ≤ B ≤ D - C,  D = 任意数,  n = 任意数。

譬如:  主帖 = {C,B,D} ={2,4,6}。

孤立路数量 = \(\D\bigg(\frac{((4 - 0) + n)!\ \ }{(4 - 0)! n!}\bigg)\bigg(\frac{((6 - 2) + n)!\ \ }{(6 - 2)! n!}\bigg) - \bigg(\frac{((6 - 0) + n)!\ \ }{(6 - 0)! n!}\bigg)\bigg(\frac{((4 - 2) + n)!\ \ }{(4 - 2)! n!}\bigg)\)

n = 1, 2, 3, 4, 5, 6, ...,  得到这样一串数: 4, 57, 385, 1750, 6174, 18228, 47124, 109890, 235950, 473473, 897897, 1623076, 2815540, 4712400, 7643472, 12058236, 18558288, 27935985, 41220025, ...

n = 4 =主帖: 孤立路数量 =1750。

再譬如:  {C,B,D} ={1,3,5}。

孤立路数量 = \(\D\bigg(\frac{((3 - 0) + n)!\ \ }{(3 - 0)! n!}\bigg)\bigg(\frac{((5 - 1) + n)!\ \ }{(5 - 1)! n!}\bigg) - \bigg(\frac{((5 - 0) + n)!\ \ }{(5 - 0)! n!}\bigg)\bigg(\frac{((3 - 1) + n)!\ \ }{(3 - 1)! n!}\bigg)\)

n = 1, 2, 3, 4, 5, 6, ...,  得到这样一串数: 2, 24, 140, 560, 1764, 4704, 11088, 23760, 47190, 88088, 156156, 264992, 433160, 685440, 1054272, 1581408, 2319786, 3335640, 4710860, 6545616, ...

再譬如:  {C,B,D} ={2,6,9}。

孤立路数量 = \(\D\bigg(\frac{((6 - 0) + n)!\ \ }{(6 - 0)! n!}\bigg)\bigg(\frac{((9 - 2) + n)!\ \ }{(9 - 2)! n!}\bigg) - \bigg(\frac{((9 - 0) + n)!\ \ }{(9 - 0)! n!}\bigg)\bigg(\frac{((6 - 2) + n)!\ \ }{(6 - 2)! n!}\bigg)\)

n = 1, 2, 3, 4, 5, 6, ...,  得到这样一串数:6, 183, 2380, 19250, 113652, 534534, 2114112, 7290855, 22493900, 63269206, 164588424, 400450232, 919413040, 2006411400, 4186514112, 8393685366, ...

通项公式不成熟。欢迎网友批评！谢谢各位网友！新年快乐！

王守恩

给出笨的解法。

记 A = (00),  C = (20),  B = (44),  D = (64),

交叉路只会出现在{23, 22, 21, 33, 32, 31, 43, 42, 41}这九个点上。

基本思路: 甲的孤立路×乙的孤立路。

甲从A——B(不过C),有55条路可走。55 = 5 + 4×3 + 3×6 + 2×10

甲的孤立路×乙的孤立路。
甲不过九个点 = 5×55,
过23,33,43 = 4×35,
过23,33 = 4×47,
过23 = 4×53,
过22,32,42,43 = 3×17,
过22,32,33,43 = 3×26,
过22,32,33 = 3×32,
过22,23,33,43 = 3×32,
过22,23,33 = 3×42,
过22,23 = 3×46,
过21,31,41,42,43 = 2×5,
过21,31,32,42 = 2×9,
过21,31,32,33,43 = 2×12,
过21,31,32,33 = 2×14,
过21,22,32,42,43 = 2×13,
过21,22,32,33,43 = 2×19,
过21,22,32,33 = 2×23,
过21,22,23,33,43 = 2×22,
过21,22,23,33 = 2×28,
过21,22,23 = 2×30,
合计: 5×55+4×(35+47+53)+3×(17+26+32+32+42+46)+2×(5+9+12+14+13+19+23+22+28+30) = 1750
55 = 5 + 4×3 + 3×6 + 2×10