有几种走法？

王守恩

northwolves 发表于 2023-12-25 20:52
测试了一下，从O出发又回到O,走了4条路, 有36种走法。
----------------------------------------------- ...

譬如: 正六边形,  共有13个点,24条路,......

9楼=6, 12, 66, 228, 966, 3756, 15186, 60420, 242166,
10楼=1, 2, 11,  38, 161,  626,   2531,  10070,  40361,   

好奇所驱，这些数据有误差吗？

目标很明确: 把"通吃"公式揪出来。
正n边形,  共有n*m+1个点, 2n*m条路,  m表示环, m可以是无穷大。

northwolves

你可以尝试证明：$a6_n=\frac{1}{78} \left(3*\ 4^{n+1}-(-1)^n \sqrt{74-26 (-1)^n} \sqrt{3}^{n+1}\right)$

northwolves

简化一下：$a_n=\frac{1}{78} \left(12*\ 4^n-(1+11 (-1)^n) 3^{\ceil \frac{n}{2}\ }\right)$

王守恩

northwolves 发表于 2023-12-29 16:54
简化一下：$a_n=\frac{1}{78} \left(12*\ 4^n-(1+11 (-1)^n) 3^{\ceil \frac{n}{2}\ }\right)$

贪心的问：1, 2, 9, 30, 113, 410, 1513, 5558, ......, 还可以有吗？

northwolves

王守恩 发表于 2023-12-29 18:24
贪心的问：1, 2, 9, 30, 113, 410, 1513, 5558, ......, 还可以有吗？

这个有点复杂，晚上回去帮你算一算

aimisiyou

王守恩 发表于 2023-12-29 18:24
贪心的问：1, 2, 9, 30, 113, 410, 1513, 5558, ......, 还可以有吗？

转移矩阵都可以列出来，不就是求矩阵幂吗？

northwolves

王守恩 发表于 2023-12-29 18:24
贪心的问：1, 2, 9, 30, 113, 410, 1513, 5558, ......, 还可以有吗？

1. d[n_]:=Round[0.059187*1.642^n+0.16474*3.68133^n-0.22393* (-1.3234)^n];Table[d[n],{n,20}]

复制代码

{1,2,9,30,113,410,1513,5558,20465,75314,277256,1020617,3757216,13831432,50917995,187445664,690049108,2540297800,9351673763,34426595454}

王守恩

aimisiyou 发表于 2023-12-26 08:34
此题可以类似于N个人传递篮球游戏，从第一人开始传球，经过K次传递后球又回到自己手里的所有方案数。只不 ...

谢谢 aimisiyou！继续学习。
"回"字外面再添一个框后添两条对角线,  共有13个点,24条路,  记对角线的交点=O,
从O出发又回到O,走了2条路, 有4种走法。
从O出发又回到O,走了3条路, 有8种走法。
从O出发又回到O,走了4条路, 有36种走法。
从O出发又回到O,走了5条路, 有120种走法。
从O出发又回到O,走了6条路, 有456种走法。
......
从O出发又回到O,走了9条路，有几种走法？

aimisiyou

王守恩 发表于 2023-12-30 12:54
谢谢 aimisiyou！继续学习。
"回"字外面再添一个框后添两条对角线,  共有13个点,24条路,  记对角线的交点= ...

掌握了方法就没必要一个接一个刷题了。

王守恩

先把目前的成果晒一晒。渴望有网友找出反例来。
1,允许中途经过O。
正3边形,  共有07个点,12条路,......
{3, 6, 24, 78, 276, 960, 3372, 11832, 41568, 146040, 513168, 1803264, 6336816,
正4边形,  共有09个点,16条路,......
{4, 8, 36, 120, 452, 1640, 6052, 22232, 81860, 301256, 1109028,4082488,15028932,
正5边形,  共有11个点,20条路,......
{5, 10, 50, 170, 680, 2560, 9900, 37920, 145880, 560360, 2154000, 8277920, 31816080,
正6边形,  共有13个点,24条路,......
{6, 12, 66, 228, 966, 3756, 15186, 60420, 242166, 967692, 3872226, 15485988, 61948326,
正7边形,  共有15个点,28条路,......
{7, 14, 84, 294, 1316, 5264, 22204, 91448, 380912, 1578584, 6557712, 27212416, 112980336,
正8边形,  共有17个点,32条路,......
{8, 16, 104, 368, 1736, 7120, 31272, 132912, 574088, 2460560, 10586088, 45461744,195408456,
正9边形,  共有19个点,36条路,......
{9, 18, 126, 450, 2232, 9360, 42732, 186912, 835560, 3694536,  16427088,  72835488,  323402832,
......  ......
2, 不允许中途经过O。
正3边形,  共有07个点,12条路,......
{3, 6, 15, 42, 123, 366, 1095, 3282, 9843, 29526, 88575, 265722, 797163, 2391486,
正4边形,  共有09个点,16条路,......
{4, 8, 20, 56, 164, 488, 1460, 4376,13124, 39368,118100, 354296,1062884, 3188648,
正5边形,  共有11个点,20条路,......
{5, 10, 25, 70, 205, 610, 1825, 5470,16405, 49210,147625, 442870,1328605, 3985810,
正6边形,  共有13个点,24条路,......
{6, 12, 30, 84, 246, 732, 2190, 6564,19686, 59052, 177150, 531444, 1594326, 4782972,
正7边形,  共有15个点,28条路,......
{7, 14, 35, 98, 287, 854, 2555, 7658, 22967, 68894, 206675, 620018, 1860047, 5580134,
正8边形,  共有17个点,32条路,......
{8, 16, 40, 112, 328, 976, 2920, 8752, 26248, 78736, 236200, 708592, 2125768, 6377296,
正9边形,  共有19个点,36条路,......
{9, 18, 45, 126, 369, 1098, 3285, 9846, 29529, 88578, 265725, 797166, 2391489, 7174458,
......  ......