本帖最后由 aimisiyou 于 2025-3-2 12:30 编辑
来个好理解的。对于两层情形，就是找两条路径，1、两条路径除了首尾中间无交点；2、两条路径上不存在两点的斜率为-3/2（除了尾端）。
本帖最后由 四来 于 2025-3-2 21:44 编辑
两层的公式有了，等我把多层的搞出来再细说，如果一直没说的话就是没搞出来.
L W(L,2)
5 2
6 2
7 2
8 4
9 6
10 8
11 12
12 18
13 26
14 38
15 56
16 82
17 120
18 176
19 258
20 378
21 554
22 812
23 1190
24 1744
25 2556
26 3746
27 5490
28 8046
29 11792
30 17282
31 25328
32 37120
33 54402
34 79730
35 116850
36 171252
37 250982
38 367832
39 513048
40 522364
...................
mathe可否给出墙高是5的数据，要超过40组， 低于40组Mathematica无法推导出递推公式。
我现在的Mathematica代码占用内存小，时间复杂度却是顶点数的平方，导致计算宽为40的时候超级慢。
另外，图的顶点数和边数都是指数级增长,且存在确定的表达式。
顶点数的递推公式是$V_{n+3} = V_{n+1}+V_{n},V_5=V_6=2,V_7=3$, 边数的递推公式是$E_{n+3} = E_{n+2}+E_{n},E_5=E_6=E_7=2$
W(5,5)=2
W(6,5)=2
W(7,5)=2
W(8,5)=4
W(9,5)=14
W(10,5)=28
W(11,5)=46
W(12,5)=96
W(13,5)=216
W(14,5)=462
W(15,5)=890
W(16,5)=1796
W(17,5)=3920
W(18,5)=7958
W(19,5)=16282
W(20,5)=33666
W(21,5)=69062
W(22,5)=144690
W(23,5)=294652
W(24,5)=607244
W(25,5)=1263372
W(26,5)=2582356
W(27,5)=5359710
W(28,5)=11023578
W(29,5)=22683244
W(30,5)=47054902
W(31,5)=96479564
W(32,5)=199541122
W(33,5)=411769192
W(34,5)=846623978
W(35,5)=1752549168
W(36,5)=3604474740
W(37,5)=7438075718
W(38,5)=15361315212
W(39,5)=31603683084
W(40,5)=65314441722
W(41,5)=134570819852
W(42,5)=277409737620
W(43,5)=572878549596
W(44,5)=1179665905128
W(45,5)=2435167456590
W(46,5)=5021670418456
W(47,5)=10349248760526
W(48,5)=21364297680838
W(49,5)=44024681962040
W(50,5)=90818438239672
W(51,5)=187343388013694
W(52,5)=386133652814576
W(53,5)=796795317310884
W(54,5)=1642694128401338
W(55,5)=3387637211933096
W(56,5)=6988503142954480
W(57,5)=14406691888418976
W(58,5)=29719699158425594
W(59,5)=61286490181499014
W(60,5)=126374376975666006
W(61,5)=260686834754014802
W(62,5)=537494251573944652
W(63,5)=1108598116686465380
W(64,5)=2286350245225684724
W(65,5)=4714504770847821054
W(66,5)=9724295251403158074
W(67,5)=20052364907008872254
W(68,5)=41354692676199938356
W(69,5)=85291675299979899122
W(70,5)=175879567486340276034
W(71,5)=362748473133797493156
W(72,5)=748073071175362781172
W(73,5)=1542719068314230368608
W(74,5)=3181748468873313949712
W(75,5)=6561329125701136280570
W(76,5)=13531962767099736573516
W(77,5)=27907067333908383937388
W(78,5)=57551129848287320652682
W(79,5)=118692966339901071089842
W(80,5)=244773444282742479104410
W(81,5)=504802448217164709294486
W(82,5)=1041070510904091279803258
W(83,5)=2146951340184829913155734
W(84,5)=4427777007228822619427778
W(85,5)=9131318103835287318418978
W(86,5)=18831517004372284464587024
W(87,5)=38836887061653420657343796
W(88,5)=80092202677597423177190664
W(89,5)=165176511383408879996231640
W(90,5)=340643769841204723232406774
W(91,5)=702507073922270814663033728
W(92,5)=1448799748993384336153274860
W(93,5)=2987840792194445231298428396
W(94,5)=6161865570793092475875476738
W(95,5)=12707678235955210465493769442
W(96,5)=26206959455305572731983884264
W(97,5)=54047121239567005480031597414
W(98,5)=111461242192362478890568111770
W(99,5)=229867207002811748347485612624
W(100,5)=474057937561300450093411541440
另外附件中是墙高6,7,8的数据
上接19楼。2，3，4层高的是分别是3，9，12阶差分方程，
基于楼上的数据，5层高的墙的递推公式竟然一下子蹦到了30阶
以下给出的是${a_1,\ldots ,a_d}$,代表着线性方程的系数，$W(d+k)=a_1 W(d+k-1)+\cdots+a_d W(k)$
{0,1,10,0,5,-45,1,-30,120,0,41,-210,2,0,252,0,-41,-210,1,30,120,0,-5,-45,0,-1,10,0,0,-1}
$W(n+30)=-W(n)+10 W(n+3)-W(n+4)-45 W(n+6)-5 W(n+7)+120 W(n+9)+30 W(n+10)+W(n+11)-210 W(n+12)-41 W(n+13)+252 W(n+15)+2 W(n+17)-210 W(n+18)+41 W(n+19)+120 W(n+21)-30 W(n+22)+W(n+23)-45 W(n+24)+5 W(n+25)+10 W(n+27)+W(n+28)$
6层高的墙的递推公式是48阶
{1,0,16,-7,7,-121,2,-56,554,169,182,-1786,-918,-278,4369,2705,105,-8254,-5313,342,12001,7349,-594,-13430,-7315,336,11686,5279,103,-8009,-2712,-280,4334,923,182,-1814,-168,-56,561,-1,7,-120,7,0,16,-1,0,-1}
7层高的墙的递推公式是105阶
{0,1,35,0,21,-595,7,-742,6546,-189,8442,-52360,1625,-51800,324781,-6769,173331,-1623160,21135,-86338,6720337,-125573,-2490701,-23522821,904733,16262632,70564735,-4533690,-62843522,-183276015,15618238,177893656,415941079,-38837182,-393332646,-831525031,71974112,695726402,1472717778,-100960652,-986540751,-2318102678,108116805,1096386754,3248633402,-91247312,-880062205,-4060767464,70966841,338986285,4536729139,-70969158,338885006,-4536877408,91246008,-880017579,4061785675,-108117870,1096423708,-3251563183,100961150,-986622504,2322886169,-71974344,695802674,-1477622622,38837557,-393380428,834755181,-15618292,177910802,-417268625,4533690,-62844685,183592395,-904730,16262064,-70611643,125573,-2490789,23535820,-21135,-86338,-6724371,6769,173328,1623160,-1625,-51800,-324631,189,8442,52360,-7,-742,-6545,0,21,595,0,1,-35,0,0,1}
8层高的墙的递推公式是192阶
{1,0,64,-37,37,-2025,422,-1765,41695,4759,40381,-629197,-252083,-587864,7472820,4887824,6065106,-73274918,-63692988,-46409045,612978228,636440791,263744236,-4470523241,-5171542910,-1032476433,28802662967,35347828236,1665035181,-165149843780,-207788094350,12588010457,846193157740,1067141660849,-141704696448,-3885046612280,-4844488792475,849318642208,16024084617943,19615394076878,-3771509673073,-59547041296244,-71337272469560,13335250458658,200034815511122,234321838022051,-37975158009051,-609702614158434,-698224433039659,83776960736255,1692890801213440,1893979213952980,-118336748660393,-4300070104855334,-4689584899735748,-43819861772932,10037141040123029,10620897693413048,1011416781676744,-21633289496286150,-22032498629924891,-4318066436678249,43276666133303758,41894263253630301,13147713241940825,-80791274754425684,-73013388809072720,-33070315082534338,141524296420318829,116502294544538065,72282138213546000,-233805858117944594,-169765180923899850,-140635198435709217,365776959175134404,224828585377528115,246886208168074602,-543294340852810873,-268227585217763380,-394309985372544717,766740661704974264,283438400586595564,575998604181513095,-1027179140092256634,-255828538005201812,-772214655361900053,1303345264698855641,178626536437117236,952197917760982589,-1561784478771152459,-57336889456059125,-1081269458196541351,1762011134601861425,-89820275602356770,1131364008542629966,-1866446591841957386,236290202034913840,-1090759530883815531,1851993206007695085,-354964454550466632,968468056182266782,-1718327749170321289,426249099171071247,-791068031518974467,1488873216933720926,-443176909326370830,593468708928896570,-1203728322489856021,411806020137950164,-407939516068067888,907654578468660958,-347355847826705674,256048725419869699,-638246568017727956,268237392000032444,-146028041662605482,418627555334871929,-190557832490949940,75117029146200485,-256249811806610714,124868709734196948,-34448178690646885,146496384323573258,-75568141898477372,13801928961628077,-78290656371406608,42245511943274268,-4638903847062031,39146179890937812,-21804119712974394,1175540594371239,-18323919810453575,10377482284276677,-127316227347546,8029657374390619,-4546441861404687,-78640981233723,-3291137068358692,1829242281211989,66909853913107,1259254613530646,-673973009191707,-31734482294082,-448373196291797,226607485091996,11357575607549,147938474086442,-69239479044684,-3242114097174,-44996808051368,19129617299220,731453036934,12541690963450,-4750104505922,-120310589621,-3182430623067,1052263840374,9507289129,729988959603,-206038966024,2004308590,-150212154839,35238732190,-1060025788,27495833035,-5181798399,265491476,-4434394781,640811389,-46543563,622920601,-64450653,6079995,-75126406,4975495,-589009,7630692,-259127,40409,-635346,5120,-1764,41655,413,37,-2016,-37,0,64,1,0,-1}
这个阶数还能递增的这么迅速，看样子也是指数级别的，再下去递推公式的优势就不明显了。。。
。
。
王守恩 发表于 2025-2-28 08:32
换个方向试试 ？
已知W(9,3)=8, W(9,8)=34, W(9,18)=1026。
比如这个W(9,.)的递推式，我们可以直接让计算机对每个连同分支的图求特征多项式，然后求所有特征多项式的最小公倍数最为最终递推式的特征多项式。只是这个结果可能不是最小的。
比如王守恩这个计算结果相当于特征多项式为\(x^3-x^2-2x+2\)
而使用上面方法计算机计算结果为\(x^5 - 3x^3 + 2x\)，多了倍数\((x+1)x\). 其中特征多项式次数最高的子图的次数为3.
通过这种方法得出
W(10,.): x^7 - 4*x^5 + 4*x^3 - x ，子图最高4次
W(11,.):x^5 - 4*x^3 + 3*x，子图最高5次
W(12,.):x^12 - 9*x^10 + 29*x^8 - 40*x^6 + 22*x^4 - 3*x^2，子图最高6次
W(13,.):x^15 - 13*x^13 + 63*x^11 - 146*x^9 + 175*x^7 - 110*x^5 + 34*x^3 - 4*x，子图最高7次
W(14,.):x^17 - 17*x^15 + 109*x^13 - 344*x^11 + 573*x^9 - 490*x^7 + 184*x^5 - 16*x^3，子图最高9次
W(15,.):x^27 - 28*x^25 + 329*x^23 - 2148*x^21 + 8645*x^19 - 22420*x^17 + 38000*x^15 - 41857*x^13 + 29336*x^11 - 12617*x^9 + 3144*x^7 - 405*x^5 + 20*x^3，子图最高12次
W(16,.):x^32 - 39*x^30 + 648*x^28 - 6057*x^26 + 35469*x^24 - 137156*x^22 + 359693*x^20 - 647050*x^18 + 798802*x^16 - 670391*x^14 + 374440*x^12 - 133885*x^10 + 28550*x^8 - 3150*x^6 + 125*x^4，子图最高16次
W(17,.):x^44 - 58*x^42 + 1481*x^40 - 22165*x^38 + 218326*x^36 - 1505194*x^34 + 7531834*x^32 - 27960219*x^30 + 77956091*x^28 - 164056094*x^26 + 260253028*x^24 - 308925293*x^22 + 270634440*x^20 - 171363637*x^18 + 76198360*x^16 - 22919841*x^14 + 4445870*x^12 - 518005*x^10 + 31825*x^8 - 750*x^6，子图最高20次
W(18,.):x^59 - 87*x^57 + 3432*x^55 - 81936*x^53 + 1331682*x^51 - 15699637*x^49 + 139591517*x^47 - 960334317*x^45 + 5201502904*x^43 - 22446117132*x^41 + 77788723140*x^39 - 217583601972*x^37 + 492524413528*x^35 - 902919327054*x^33 + 1339389826888*x^31 - 1603902157185*x^29 + 1544593038924*x^27 - 1189884760354*x^25 + 728062423769*x^23 - 350558818599*x^21 + 131211772897*x^19 - 37563541704*x^17 + 8047167606*x^15 - 1251439159*x^13 + 135172992*x^11 - 9462960*x^9 + 379296*x^7 - 6480*x^5，子图最高25次
W(19,.):x^82 - 128*x^80 + 7571*x^78 - 276077*x^76 + 6982667*x^74 - 130623727*x^72 + 1881524392*x^70 - 21447401937*x^68 + 197309342017*x^66 - 1486521749375*x^64 + 9274096965142*x^62 - 48324773997324*x^60 + 211712257401667*x^58 - 783816869647939*x^56 + 2461746876255817*x^54 - 6577108005415841*x^52 + 14975534923377162*x^50 - 29087440532797351*x^48 + 48202935027929644*x^46 - 68110546000593703*x^44 + 81943554978029097*x^42 - 83754722883320371*x^40 + 72503468005339544*x^38 - 52944003536191459*x^36 + 32447451925152282*x^34 - 16585265854987402*x^32 + 7016052451239801*x^30 - 2433230769473699*x^28 + 683795203196415*x^26 - 153458602055911*x^24 + 26996660519681*x^22 - 3633172746804*x^20 + 361754032500*x^18 - 25389807696*x^16 + 1163837808*x^14 - 30373056*x^12 + 326592*x^10，子图最高30次
W(20,.):x^104 - 187*x^102 + 16383*x^100 - 897153*x^98 + 34564448*x^96 - 999681883*x^94 + 22613835584*x^92 - 411544643762*x^90 + 6150296979404*x^88 - 76654955569846*x^86 + 806442474693413*x^84 - 7229866991805873*x^82 + 55657866393309517*x^80 - 370204272607195050*x^78 + 2138187877544462995*x^76 - 10766988776296012879*x^74 + 47423296695777894834*x^72 - 183165726474820354767*x^70 + 621578593313955725012*x^68 - 1855917455604859519327*x^66 + 4880138710264003124095*x^64 - 11306334800959032613765*x^62 + 23080770925669189574717*x^60 - 41501751282738861279349*x^58 + 65682740944818415704105*x^56 - 91394841550967295270056*x^54 + 111642982074056172779574*x^52 - 119500560318317578545011*x^50 + 111830045041478888549765*x^48 - 91252184962720381598544*x^46 + 64726864705165594807092*x^44 - 39768688259227597590643*x^42 + 21078950555790086760800*x^40 - 9593791316558003880479*x^38 + 3729531477360207366185*x^36 - 1230786726735184070131*x^34 + 342371789008725467432*x^32 - 79616820946946633532*x^30 + 15327035808439169143*x^28 - 2414214857481766507*x^26 + 306738660749453408*x^24 - 30883611992245831*x^22 + 2408615474032257*x^20 - 141148493360693*x^18 + 5953088171856*x^16 - 169048071360*x^14 + 2867946480*x^12 - 21781872*x^10，子图最高40次
谢谢mathe！有您这4个数垫底。答案错不了！
已知W(13,3)=52, W(13,8)=2052, W(13,18)=5419032, W(13,28)=17172927220。
W(13,1)=16,
W(13,2)=26,
W(13,3)=52,
W(13,4)=104,
W(13,5)=216,
W(13,6)=452,
W(13,7)=960,
W(13,8)=2052,
W(13,9)=4426,
W(13,10)=9594,
W(13,11)=20932,
W(13,12)=45842,
W(13,13)=100876,
W(13,14)=222604,
W(13,15)=492920,
W(13,16)=1093718,
W(13,17)=2432758,
W(13,18)=5419032,
{16, 26, 52, 104, 216, 452, 960, 2052, 4426, 9594, 20932, 45842, 100876, 222604, 492920, 1093718, 2432758, 5419032,
12091774, 27008396, 60398204, 135161892, 302718934, 678319858, 1520800788, 3410777986, 7652442340, 17172927220, 38547932488, 86541460254}
LinearRecurrence[{2, 5, -9, -6, 8, 2, -2}, {14, 24, 50, 102, 214, 450, 958, 2050}, 30] + 2
谢谢mathe！有您这4个数垫底。答案错不了。就是不知道怎么把这3个数合并了？
已知W(14,3)=84, W(14,8)=6932, W(14,18)=94385908, W(14,28)=1396582222520=1396403339264+178883252+4。
W(14,1)=9+8+4=21,
W(14,2)=20+14+4=38,
W(14,3)=54+26+4=84,
W(14,4)=136+48+4=188,
W(14,5)=368+90+4=462,
W(14,6)=928+168+4=1096,
W(14,7)=2512+316+4=2828,
W(14,8)=6336+592+4=6932,
W(14,9)=17152+1114+4,
W(14,10)=43264+2090+4,
W(14,11)=117120+3932+4,
W(14,12)=295424+7382+4,
W(14,13)=799744+13884+4,
W(14,14)=2017280+26076+4,
W(14,15)=5460992+49032+4,
W(14,16)=13774848+92110+4,
W(14,17)=37289984+173170+4,
W(14,18)=94060544+325360+4=94385908,
{20, 54, 136, 368, 928, 2512, 6336, 17152, 43264, 117120, 295424, 799744, 2017280, 5460992, 13774848, 37289984, 94060544,
254631936, 642285568, 1738735616, 4385800192, 11872829440, 29948116992, 81072750592, 204498534400, 553599369216, 1396403339264, 3780212948992, 9535238438912, 25812908638208}
LinearRecurrence[{0, 8, 0, -8}, {3, 8, 20, 54}, 30]
{14, 26, 48, 90, 168, 316, 592, 1114, 2090, 3932, 7382, 13884, 26076, 49032, 92110, 173170, 325360, 611618, 1149248, 2160212, 4059360, 7629882, 14338290, 26949004, 50644750, 95185300, 178883252, 336200648, 631835054, 1187485194}
LinearRecurrence[{1, 3, -2, -1}, {4, 4, 8, 14}, 30]
王守恩 发表于 2025-3-4 10:50
谢谢mathe！有您这4个数垫底。答案错不了。就是不知道怎么把这3个数合并了？
已知W(14,3)=84, W(14,8)=693 ...
来一串 W(L,3) , L 从 5 到 20 就够了，多谢.
mathe 发表于 2025-3-2 21:18
另外附件中是墙高6,7,8的数据
mathe，你那个 .out格式文件用什么软件打开？