找回密码
 欢迎注册
楼主: 王守恩

[求助] 从3×3网格的左下角到右上角有几种走法?

[复制链接]
发表于 2021-4-23 14:23:29 | 显示全部楼层

捕获.PNG
从图线看,貌似\[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)\]

点评

参考论文,结论一致:https://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_13_64/tcstr_13_64.pdf  发表于 2021-4-23 19:18

评分

参与人数 1威望 +6 金币 +6 贡献 +6 经验 +6 鲜花 +6 收起 理由
wayne + 6 + 6 + 6 + 6 + 6 跟论文的结论一致!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-4-23 18:29:59 | 显示全部楼层
拟合也是猜~
与其猜不如先搜搜,
这增长速度,太恐怖了。
  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
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-4-23 19:04:06 | 显示全部楼层

$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}]}]}]
复制代码



毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-4-23 20:23:03 | 显示全部楼层
$f(m,n)$的结果  https://oeis.org/FinchMarxen.html

评分

参与人数 1威望 +24 金币 +24 贡献 +24 经验 +24 鲜花 +24 收起 理由
王守恩 + 24 + 24 + 24 + 24 + 24 及时雨!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-4-24 10:58:59 | 显示全部楼层
本帖最后由 王守恩 于 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 11:47:21 | 显示全部楼层
王守恩 发表于 2021-4-24 10:58
4种基本走法:往左走=1,往上走=2,往右走=3,往下走=4,
用这样的一串数来表示1种走法
第1个数字表 ...

这就是bfs思路啊,每种状态不断往前搜索一步
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-4-24 14:15:53 | 显示全部楼层
本帖最后由 王守恩 于 2021-4-24 14:30 编辑
aimisiyou 发表于 2021-4-24 11:47
这就是bfs思路啊,每种状态不断往前搜索一步


这题目比想象当中要难,通项公式不太好找。从简单的算起。
  
从网格的左下点到右上点,沿着网线走,有几种走法(网线,格点都不能重复)。

+----+----+----+   
|      |     |      |           
+----+----+----+   
|      |      
+----+-
|      |        
+----+--

我们称上图的方格(3*3-2*2)为 F(3),则 F(n) 可以有通项公式吗 ?
                          n*n-(n-1)*(n-1)= F(n)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-5-1 10:11:22 | 显示全部楼层
王守恩 发表于 2021-4-24 14:15
这题目比想象当中要难,通项公式不太好找。从简单的算起。
  
从网格的左下点到右上点,沿着网线走 ...

这题目比想象当中要难,通项公式不太好找。
谢谢 aimisiyou:可以通过编写程序来计算F(m,n),不代表就能得出其显式通项。
谢谢  kastin  :这个问题没有解析表达式。
只有简单的才可能有,
譬如21楼 n*n-(n-1)*(n-1)
F(n)=7*4^n
譬如  n*n-(n-2)*(n-2)

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2025-4-26 15:21 , Processed in 0.036988 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

快速回复 返回顶部 返回列表