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 13:59 编辑
王守恩 发表于 2021-4-22 08:18
我的目标很明确，搜集这样一个通项公式：
从 m×n 网格的左下点(S)到右上点(F)，沿着网线走，有几种走法 ...
m×n1 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 112845221634967110272336067810
本帖最后由 aimisiyou 于 2021-4-23 07:46 编辑
王守恩 发表于 2021-4-22 13:57
m×n1 2 3 4 5 6
1 1 1 1 1 ...
编程序求解了下，增长太快，只能求很小的几个数据。（坐标从0，0开始）
mathe 发表于 2021-4-20 12:43
找到答案了
https://bbs.emath.ac.cn/thread-517-1-1.html
从图线看，貌似\那么也许\@wayne 拟合一哈，你的强项。
不过这么瞎猜肯定撞墙，适度的猜想应该是：\[\ln(f(n,n))=O(n^2)\\\ln(f(m,n))=O(mn)\]
拟合也是猜~
与其猜不如先搜搜，:*-^
这增长速度，太恐怖了。
1
2
12
184
8512
1262816
575780564
789360053252
3266598486981642
41044208702632496804
1568758030464750013214100
182413291514248049241470885236
64528039343270018963357185158482118
69450664761521361664274701548907358996488
227449714676812739631826459327989863387613323440
2266745568862672746374567396713098934866324885408319028
68745445609149931587631563132489232824587945968099457285419306
6344814611237963971310297540795524400449443986866480693646369387855336
1782112840842065129893384946652325275167838065704767655931452474605826692782532
1523344971704879993080742810319229690899454255323294555776029866737355060592877569255844
3962892199823037560207299517133362502106339705739463771515237113377010682364035706704472064940398
31374751050137102720420538137382214513103312193698723653061351991346433379389385793965576992246021316463868
755970286667345339661519123315222619353103732072409481167391410479517925792743631234987038883317634987271171404439792
55435429355237477009914318489061437930690379970964331332556958646484008407334885544566386924020875711242060085408513482933945720
12371712231207064758338744862673570832373041989012943539678727080484951695515930485641394550792153037191858028212512280926600304581386791094
8402974857881133471007083745436809127296054293775383549824742623937028497898215256929178577083970960121625602506027316549718402106494049978375604247408
17369931586279272931175440421236498900372229588288140604663703720910342413276134762789218193498006107082296223143380491348290026721931129627708738890853908108906396
$f=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}\]
拟合代码：
ans=Import["https://oeis.org/A007764/b007764.txt","Data"];
data=Table[{p[],Log]]},{p,ans}];
nlm=NonlinearModelFit (n^2+b n +c),{a,b,c},n];
nlm["ParameterConfidenceIntervalTable"]
GraphicsRow[{ListPlot,Filling->Axis],Show[{ListPlot],Plot,{x,0,30}]}]}]
$f(m,n)$的结果https://oeis.org/FinchMarxen.html
本帖最后由 王守恩 于 2021-4-24 11:10 编辑
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条线，让题目回到熟悉的网格上来。
王守恩 发表于 2021-4-24 10:58
4种基本走法：往左走=1，往上走=2，往右走=3，往下走=4，
用这样的一串数来表示1种走法
第1个数字表 ...
这就是bfs思路啊，每种状态不断往前搜索一步