从3×3网格的左下角到右上角有几种走法？

aimisiyou

kastin 发表于 2021-4-21 20:24
是这个问题吗？
https://bbs.emath.ac.cn/thread-16151-1-1.html

有啥好的思路吗？

王守恩

kastin 发表于 2021-4-21 20:24
是这个问题吗？
https://bbs.emath.ac.cn/thread-16151-1-1.html

我的目标很明确，搜集这样一个通项公式：
从 m×n 网格的左下点(S)到右上点(F)，沿着网线走，有几种走法(网线,格点都不能重复)？
如同帖子《彩珠手串的配色计数》：用 m 种颜色的珠子穿手串，每串有 n 颗珠子，有多少种配色不同的手串？
可能比《彩珠手串的配色计数》还要难。参考A145403

王守恩

王守恩 发表于 2021-4-22 08:18
我的目标很明确，搜集这样一个通项公式：
从 m×n 网格的左下点(S)到右上点(F)，沿着网线走，有几种走法 ...

m×n  1    2       3         4          5              6
   1    1    1       1         1          1              1
   2    1    2       4         8         16             32
   3    1    4      12       38        125           414
   4    1    8      38      184       976           5382
   5    1   16    125      976      8512         79384
   6    1   32    414     5382    79384      1262816
   7    1   64   1369   29739   752061    20562673
   8    1  128  4522  163496  7110272  336067810

aimisiyou

王守恩 发表于 2021-4-22 13:57
m×n  1    2       3         4          5              6
   1    1    1       1         1       ...

编程序求解了下，增长太快，只能求很小的几个数据。（坐标从0，0开始）

hujunhua

mathe 发表于 2021-4-20 12:43
找到答案了
https://bbs.emath.ac.cn/thread-517-1-1.html

从图线看，貌似\[f(n,n)=2^{an^2+bn+c}\]那么也许\[f(m,n)=2^{am^2+bmn+cn^2+dm+en+f}\]@wayne 拟合一哈，你的强项。

不过这么瞎猜肯定撞墙，适度的猜想应该是：\[\ln(f(n,n))=O(n^2)\\\ln(f(m,n))=O(mn)\]

wayne

拟合也是猜~
与其猜不如先搜搜，
这增长速度，太恐怖了。

1. 1
   
2. 2
   
3. 12
   
4. 184
   
5. 8512
   
6. 1262816
   
7. 575780564
   
8. 789360053252
   
9. 3266598486981642
   
10. 41044208702632496804
    
11. 1568758030464750013214100
    
12. 182413291514248049241470885236
    
13. 64528039343270018963357185158482118
    
14. 69450664761521361664274701548907358996488
    
15. 227449714676812739631826459327989863387613323440
    
16. 2266745568862672746374567396713098934866324885408319028
    
17. 68745445609149931587631563132489232824587945968099457285419306
    
18. 6344814611237963971310297540795524400449443986866480693646369387855336
    
19. 1782112840842065129893384946652325275167838065704767655931452474605826692782532
    
20. 1523344971704879993080742810319229690899454255323294555776029866737355060592877569255844
    
21. 3962892199823037560207299517133362502106339705739463771515237113377010682364035706704472064940398
    
22. 31374751050137102720420538137382214513103312193698723653061351991346433379389385793965576992246021316463868
    
23. 755970286667345339661519123315222619353103732072409481167391410479517925792743631234987038883317634987271171404439792
    
24. 55435429355237477009914318489061437930690379970964331332556958646484008407334885544566386924020875711242060085408513482933945720
    
25. 12371712231207064758338744862673570832373041989012943539678727080484951695515930485641394550792153037191858028212512280926600304581386791094
    
26. 8402974857881133471007083745436809127296054293775383549824742623937028497898215256929178577083970960121625602506027316549718402106494049978375604247408
    
27. 17369931586279272931175440421236498900372229588288140604663703720910342413276134762789218193498006107082296223143380491348290026721931129627708738890853908108906396

复制代码

wayne

$f[n]=1.74353^(1.29677 -2.00774 n+n^2)$, 拟合效果：

\[\begin{array}{l|lll}
\text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\
\hline
a & 1.74353 & 0.000276745 & \{1.74296,1.7441\} \\
b & -2.00774 & 0.00768237 & \{-2.02359,-1.99188\} \\
c & 1.29677 & 0.0497598 & \{1.19407,1.39947\} \\
\end{array}\]

拟合代码：

1. ans=Import["https://oeis.org/A007764/b007764.txt","Data"];
   
2. data=Table[{p[[1]],Log[p[[2]]]},{p,ans}];
   
3. nlm=NonlinearModelFit[data,Log[a] (n^2+b n +c),{a,b,c},n];
   
4. nlm["ParameterConfidenceIntervalTable"]
   
5. GraphicsRow[{ListPlot[nlm["FitResiduals"],Filling->Axis],Show[{ListPlot[data,PlotStyle->PointSize[.02]],Plot[nlm[x],{x,0,30}]}]}]

复制代码

wayne

$f(m,n)$的结果  https://oeis.org/FinchMarxen.html

王守恩

aimisiyou 发表于 2021-4-21 14:08
除了BFS，难道还有什么其它算法吗？

4种基本走法：往左走=1，往上走=2，往右走=3，往下走=4，
用这样的一串数来表示1种走法
第1个数字表示所在位置，第2个数字表示走法，只有如下可能
1+1,1+2,1+4，2+1,2+2,2+3，3+2,3+3,3+4，4+1,4+3,4+4
前面的数是1(3),后面的数不会是3(1)，前面的数是2(4),后面的数不会是4(2)，
边上的点往前，只有2条路可走，中间的点往前，只有3条路可走，
从左下点出发,有2条路可走：1,2，把出发点连同2条路抹去，变成2道题，答案不变
我们总可以一次又一次不断的抹去2条线,3条线，让题目回到熟悉的网格上来。

aimisiyou

王守恩 发表于 2021-4-24 10:58
4种基本走法：往左走=1，往上走=2，往右走=3，往下走=4，
用这样的一串数来表示1种走法
第1个数字表 ...

这就是bfs思路啊，每种状态不断往前搜索一步