有多少条路径：通过一个含单向边的蜂窝状网络

hujunhua

通过一个蜂巢状网络从A走到B，其中有向边只能单向通过，任何边都不许重复经过。问有多少条可行路径。

nyy

我只会一个思路，穷举法！然后看其中哪些是符合要求的。给每一个节点搞上编号，然后全排列，
然后看哪些排列符合要求，删除掉那些不符合要求的排列，然后问题解决。
这是我能想到的唯一的解决办法！

hujunhua

设白色反向箭头为 n 个，则路径层数为 `2n+1`, 记第 i 层的路径数为 `{a_i}`, \[\begin{equation}a_i=\begin{cases}
i+1, & \text{ if } i\le n+1\\
2n+3-i, & \text{ if } i >n+1
\end{cases}\end{equation}\]不通过任何白色箭头的路径数为\[\begin{equation} a_1\cdot(a_2-1)\cdot a_3\cdot\cdots\cdot(a_{2n}-1)\cdot a_{2n+1}:=A \end{equation}\]
一、假定不通过第i-2层和第i+2层、只通过第 i 层的白色箭头，则仅影响第i-1和第i+1层的可行路径，不会影响更远。相关的路径可分为两类：
1、通过前一层和第 i 层的上半层，过白色箭头后转到第 i 层和后一层的下半层，所以该类路径数为\[\begin{equation}
\frac{a_{i-1}}2\cdot\frac{a_{i}-1}2\cdot\frac{a_{i}-1}2\cdot\frac{a_{i+1}}2
\end{equation}\]2、上述路径的镜像路径。
所以总的可选路径数为2·(3), 即\[\begin{equation}
\frac{a_{i-1}\cdot(a_{i}-1)^2\cdot a_{i+1}}8
\end{equation}\]相对于不过白色箭头通过这3层的路径数\(a_{i-1}(a_i-1)a_{i+1}\)，单独通过第 i 层白色箭头产生的路径倍增系数为\[\begin{equation}\frac{a_{i}-1}8\end{equation}\]
二、假定不通过第i-4层和第i+2层、只通过第 i-2 层和第 i 层的白色箭头，则将影响第i-3，i-1和i+1层的可行路径，不会影响更远。相关的路径可分为两类：
1、通过前一层和第 i-2 层的上半层，过 i-2 层的白色箭头后转到第 i-1 层和第 i 层下半层，通过第 i 层白色箭头后转到第 i 层和第 i+1 层上半层，所以该类路径数为\[\begin{equation}
\frac{a_{i-3}\cdot(a_{i-2}-1)^2\cdot a_{i-1}\cdot(a_{i}-1)^2\cdot a_{i+1}}{128}
\end{equation}\]
2、上述路径的镜像路径。
所以总的可选路径为2·(6), 即\[\begin{equation}
\frac{a_{i-3}\cdot(a_{i-2}-1)^2\cdot a_{i-1}\cdot(a_{i}-1)^2\cdot a_{i+1}}{64}
\end{equation}\] 相对于不过白色箭头通过这5层的路径数产生的路径倍增系数为\[\begin{equation}
\frac{a_{i-2}-1}8\cdot\frac{a_{i}-1}8
\end{equation}\]可见通过各层白色箭头的路径倍增系数不受白色箭头是否相邻的影响。
所以通过第`i_1,i_2,\cdots,i_r`层白色箭头的可行路径数为\[
A\cdot \prod^r_{j=1}\frac{a_{i_j}-1}8\tag{9}\]
故全部可行路径数为\[
A \sum_{遍历组合}\cdot \prod^r_{j=1}\frac{a_{i_j}-1}8=A\cdot\left(1+\frac{a_2-1}8\right)\left(1+\frac{a_4-1}8\right)\cdot\cdots\cdot\left(1+\frac{a_{2n}-1}8\right)\tag{10}\]
对于n=3, A=1024, 所以总路径数`=1024\cdot\left(1+\frac{3-1}8\right)\left(1+\frac{5-1}8\right)\left(1+\frac{3-1}8\right)=2400`

aimisiyou

未标记方向的边可以双向通过么？

王守恩

hujunhua 发表于 2022-11-17 14:16
设白色反向箭头为 n 个，则路径层数为 `2n+1`, 记第 i 层的路径数为 `{a_i}`, \[\begin{equation}a_i=\begi ...

闷了几天，小心翼翼还是问：
用1格(从A到第1个白箭头前面的点)：有2条路径
用4格(从A到第2个白箭头前面的点)：有10条路径
用9格(从A到第3个白箭头前面的点)：有100条路径
用16格(从A到B)：有2400条路径
站在棱形中间列看:到起点是几条路，到终点也是同样的路，

王守恩

王守恩 发表于 2022-11-21 11:33
闷了几天，小心翼翼还是问：
用1格(从A到第1个白箭头前面的点)：有2条路径
用4格(从A到第2个白箭头前面 ...

我们想要的是一条路(站在棱形中间列:看到起点是几条路，看到终点也是同样的路)
用1格(从A到第1个白箭头前面的点)：有2条路径。2=1×1×2+0×0×2
用4格(从A到第2个白箭头前面的点)：有10条路径。10=2×2×2+(2/2×1)×(2/2×1)×2，其中:2=1×2+0
用9格(从A到第3个白箭头前面的点)：有100条路径。100=5×5×4+0×0×2，其中:5=2×2+2/2×1
用16格(从A到B)：有2400条路径。2400=20×20×4+(20/2×2)×(20/2×2)×2，其中:20=5×4+0
用25格：60000=100×100×6+0×0×2，其中:100=20×4+20/2×2
用36格：3780000=600×600×2+(600/2×3)×(600/2×3)×2，其中:600=100×6+0
用49格：162000000=4500×4500×2+0×0×2，其中:4500=600×6+600/2×3

王守恩

小心翼翼还是问：从A到B, 标准答案是多少？

hujunhua

王守恩 发表于 2022-11-26 08:05
小心翼翼还是问：从A到B, 标准答案是多少？

先把2#的(1)代入(2), 得到A的公式\[A=\begin{cases}n!!^3(n+2)!!&=2^{2n+1}k!^3(k+1)!,&\text{if }n=2k\\(n-1)!!(n+1)!!^3&=2^{2n+1}k!(k+1)!^3,&\text{if }n=2k+1\end{cases}\]再把2#的(1)代入(10), 得到确切的计算公式\[Answer=\begin{cases}\D\frac{k!^3(k+1)!(k+4)!^2}{288},&\text{if }n=2k\\\D\frac{k!(k+1)!^3(k+4)!(k+5)!}{288},&\text{if }n=2k+1\end{cases}\]
对于1楼的图，`n=3，k=1, A=2^7·2^3=2^{10}, Answer=\D\frac{2^3·5!·6!}{288}=2400`

王守恩

hujunhua 发表于 2022-11-29 00:01
先把2#的(1)代入(2), 先得到A的公式\[A=\begin{cases}n!!^3(n+2)!!&=2^{2n+1}k!^3(k+1)!,&\text{if }n=2k ...

谢谢 hujunhua ！

我们想要的是一条路。

1，把蜂窝状网络画成上下错位小方格，水平边表示单向桥，垂直边表示双向路。

2，站在中间列桥:看到起点有几条路，看到终点也有同样几条路。

3，站在任意的桥:看到起点有几条路，看到终点有几条路，两者相乘。

4，起点可以设在任意点，终点也可以设在任意点，站在桥上看是关键。

5，解一道题，抓几座关键桥，从起点到终点，总要过这几座关键桥。

6，或者说：抓住前进桥就可以，返回桥可以不管。

7，同样的，用这样的想法，去解决类似问题。