砌砖墙的趣题

aimisiyou

来个好理解的。对于两层情形，就是找两条路径，1、两条路径除了首尾中间无交点；2、两条路径上不存在两点的斜率为-3/2（除了尾端）。

四来

两层的公式有了，等我把多层的搞出来再细说，如果一直没说的话就是没搞出来.


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
...................

wayne

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$

mathe

1. W(5,5)=2
   
2. W(6,5)=2
   
3. W(7,5)=2
   
4. W(8,5)=4
   
5. W(9,5)=14
   
6. W(10,5)=28
   
7. W(11,5)=46
   
8. W(12,5)=96
   
9. W(13,5)=216
   
10. W(14,5)=462
    
11. W(15,5)=890
    
12. W(16,5)=1796
    
13. W(17,5)=3920
    
14. W(18,5)=7958
    
15. W(19,5)=16282
    
16. W(20,5)=33666
    
17. W(21,5)=69062
    
18. W(22,5)=144690
    
19. W(23,5)=294652
    
20. W(24,5)=607244
    
21. W(25,5)=1263372
    
22. W(26,5)=2582356
    
23. W(27,5)=5359710
    
24. W(28,5)=11023578
    
25. W(29,5)=22683244
    
26. W(30,5)=47054902
    
27. W(31,5)=96479564
    
28. W(32,5)=199541122
    
29. W(33,5)=411769192
    
30. W(34,5)=846623978
    
31. W(35,5)=1752549168
    
32. W(36,5)=3604474740
    
33. W(37,5)=7438075718
    
34. W(38,5)=15361315212
    
35. W(39,5)=31603683084
    
36. W(40,5)=65314441722
    
37. W(41,5)=134570819852
    
38. W(42,5)=277409737620
    
39. W(43,5)=572878549596
    
40. W(44,5)=1179665905128
    
41. W(45,5)=2435167456590
    
42. W(46,5)=5021670418456
    
43. W(47,5)=10349248760526
    
44. W(48,5)=21364297680838
    
45. W(49,5)=44024681962040
    
46. W(50,5)=90818438239672
    
47. W(51,5)=187343388013694
    
48. W(52,5)=386133652814576
    
49. W(53,5)=796795317310884
    
50. W(54,5)=1642694128401338
    
51. W(55,5)=3387637211933096
    
52. W(56,5)=6988503142954480
    
53. W(57,5)=14406691888418976
    
54. W(58,5)=29719699158425594
    
55. W(59,5)=61286490181499014
    
56. W(60,5)=126374376975666006
    
57. W(61,5)=260686834754014802
    
58. W(62,5)=537494251573944652
    
59. W(63,5)=1108598116686465380
    
60. W(64,5)=2286350245225684724
    
61. W(65,5)=4714504770847821054
    
62. W(66,5)=9724295251403158074
    
63. W(67,5)=20052364907008872254
    
64. W(68,5)=41354692676199938356
    
65. W(69,5)=85291675299979899122
    
66. W(70,5)=175879567486340276034
    
67. W(71,5)=362748473133797493156
    
68. W(72,5)=748073071175362781172
    
69. W(73,5)=1542719068314230368608
    
70. W(74,5)=3181748468873313949712
    
71. W(75,5)=6561329125701136280570
    
72. W(76,5)=13531962767099736573516
    
73. W(77,5)=27907067333908383937388
    
74. W(78,5)=57551129848287320652682
    
75. W(79,5)=118692966339901071089842
    
76. W(80,5)=244773444282742479104410
    
77. W(81,5)=504802448217164709294486
    
78. W(82,5)=1041070510904091279803258
    
79. W(83,5)=2146951340184829913155734
    
80. W(84,5)=4427777007228822619427778
    
81. W(85,5)=9131318103835287318418978
    
82. W(86,5)=18831517004372284464587024
    
83. W(87,5)=38836887061653420657343796
    
84. W(88,5)=80092202677597423177190664
    
85. W(89,5)=165176511383408879996231640
    
86. W(90,5)=340643769841204723232406774
    
87. W(91,5)=702507073922270814663033728
    
88. W(92,5)=1448799748993384336153274860
    
89. W(93,5)=2987840792194445231298428396
    
90. W(94,5)=6161865570793092475875476738
    
91. W(95,5)=12707678235955210465493769442
    
92. W(96,5)=26206959455305572731983884264
    
93. W(97,5)=54047121239567005480031597414
    
94. W(98,5)=111461242192362478890568111770
    
95. W(99,5)=229867207002811748347485612624
    
96. W(100,5)=474057937561300450093411541440
    

复制代码

wt.zip (132.03 KB, 下载次数: 5)

7 天前 上传

点击文件名下载附件

另外附件中是墙高6,7,8的数据

wayne

上接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)$

1. {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. {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阶

1. {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. {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}

复制代码

这个阶数还能递增的这么迅速，看样子也是指数级别的，再下去递推公式的优势就不明显了。。。
。

。

mathe

王守恩 发表于 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 - 3*x^3 + 2*x\)，多了倍数\((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 就够了，多谢.

iseemu2009

mathe 发表于 2025-3-2 21:18
另外附件中是墙高6,7,8的数据

mathe，你那个 .out格式文件用什么软件打开？