砌砖墙的趣题

四来

@王守恩 {2, 2, 2, 4, 6, 8, 12, 18, 26, 38, 56, 82, 120, 176, 258, 378, 554, 812, 1190, 1744, 2556, 3746, 5490, 8046, 11792, 17282, 25328, 37120}
对应的\(n\)是啥？

iseemu2009

mathe 发表于 2025-3-1 17:10

这道题是怎么分析到节点和边上去了的？能不能举例 W（9，n）是怎么弄到 5个节点和6条边上

wayne

mathe这么快就给出了答案，我又慢了一步, 我就给一个Mathematica版本的实现，内存占用也是极小。
先建图,并打印顶点和边的个数。这个过程的时间复杂度是顶点的平方,空间复杂度是边的个数.

1. w=20;offset=Ceiling[w/3];
   
2. states=Map[Most[Accumulate[#]]&,Flatten[Table[Permutations[Flatten[{ConstantArray[2,3offset-w+3c],ConstantArray[3,w-2offset-2c]}],{offset+c}],{c,0,Floor[w/2]-offset}],1]];
   
3. len=Length[states];weights=ConstantArray[{},len];
   
4. Do[If[Not@IntersectingQ[states[[i]],states[[j]]],AppendTo[weights[[i]],j];AppendTo[weights[[j]],i]],{i,1,len},{j,i+1,len}];
   
5. Print["vertex count = "<>ToString[len]<>", edge count ="<>ToString@Length[Flatten[weights]]];

复制代码

然后线性的迭代一下就可以了，这一步最快,时间复杂度是顶点的个数，比如计算的高度是h=60；

1. h=60;Transpose[{Range[h],Total/@NestList[Table[Total[#[[weights[[i]]]]],{i,len}]&,ConstantArray[1,len],h-1]}]

复制代码

wayne

现在唯一可以优化的地方就是 收集每个顶点的邻接点的集合, 目前我是 二层循环,每个循环是顶点个数,所以时间复杂度是 顶点个数的平方.
但我发现很多的顶点是有局部相似的排列特征的.这个应该利用起来, 批量跳过

mathe

发现一个奇怪的现象，我们如果对于墙的每一行结构，如果最边上有长度为3的砖块，去除，那么余下长度为3的砖块数目就代表了墙关系图中连同分支的编号。
比如长度为16的墙，
中间长度为3的砖块数目为0的连通分支，只有两个节点的线性图

中间长度为3的砖块数目为1的连通分支，有较多节点的线性图

中间长度为3的砖块数目为2的连通分支

中间长度为3的砖块数目为3的连通分支

中间长度为3的砖块数目为4的连通分支


又比如长度为18的墙
中间长度为3的砖块数目为0的连通分支，只有两个节点的线性图

中间长度为3的砖块数目为1的连通分支，有较多节点的线性图

中间长度为3的砖块数目为2的连通分支

中间长度为3的砖块数目为3的连通分支

中间长度为3的砖块数目为4的连通分支


发现规律后，得出长度为3的对应关系不难，这些对应的3正好有两格重叠。通过这个规律，可以非常容易得出给定宽度的墙的连同分支数目。另外由于不同的连通分支可以独立计算，理论上还可以将它们独立计算，增加并行度或降低内存复杂度。

wayne

按照mathe的顶点命名风格，我也画了一个图

1. w=16;
   
2. offset=Ceiling[w/3];perm=Flatten[Table[Permutations[Flatten[{ConstantArray[2,3offset-w+3c],ConstantArray[3,w-2offset-2c]}],{offset+c}],{c,0,Floor[w/2]-offset}],1];names=Table["N"<>ToString[Length[p]]<>"_"<>ToString[FromDigits[p]],{p,perm}];
   
3. states=Map[Most[Accumulate[#]]&,perm];len=Length[states];assoc={};
   
4. weights=ConstantArray[{},len];
   
5. Do[If[Not@IntersectingQ[states[[i]],states[[j]]],AppendTo[assoc,UndirectedEdge[names[[i]],names[[j]]]];AppendTo[weights[[i]],j];AppendTo[weights[[j]],i]],{i,1,len},{j,i+1,len}];Print["vertex count = "<>ToString[len]<>", edge count ="<>ToString@Length[Flatten[weights]]];
   
6. Graph[assoc,VertexLabels->"Name"]

复制代码

宽16的图:


宽18的图:

aimisiyou

根本看不懂。

yigo

yigo 发表于 2025-3-1 13:55
W(n,3):

根据这个递推方程组算出来的
\(W(n,3)=W(n-1,3)+W(n-2,3)+3W(n-3,3)-3W(n-4,3)-7W(n-6,3)+3W(n-7,3)-W(n-8,3)+4W(n-9,3)-W(n-10,3)-W(n-12,3)\)
与19#的公式不太一样，但是验证了数据是对的，估计我这个递推式的特征方程还能因式分解。

验证了下，特征方程可分解为：
\((-1 - x^2 + x^3) (-1 + 3 x^3 - x^4 - 3 x^6 - x^7 + x^9)\)
后面\(x^9\)的多项式与19#的递推式相同，
是不是我前面那个图分类太细了，还可以简化分类。

搞懂了，实际上\(X(n,3),Y(n,3),Z(n,3)\)的递推式都与19#相同，而\(W(n,3)=X(n,3)+Y(n,3)\)是他们的线性叠加，所以特征方程是一样的，只是初始值不一样。

wayne

我的跟mathe最新的数据是一致的.

1. RecurrenceTable[{a[9+n]==a[n]-3 a[3+n]+a[4+n]+3 a[6+n]+a[7+n],a[3]==0,a[4]==0,a[5]==2,a[6]==2,a[7]==2,a[8]==4,a[9]==8,a[10]==12,a[11]==18},a,{n,60}]

复制代码

王守恩

谢谢mathe！有您这4个数垫底。答案错不了！

已知W(12,3)=32, W(12,8)=502, W(12,18)=161464, W(12,28)=53632488。

W(12,1)=12,
W(12,2)=18,
W(12,3)=32,
W(12,4)=52,
W(12,5)=96,
W(12,6)=160,
W(12,7)=298,
W(12,8)=502,
W(12,9)=936,
W(12,10)=1586,
W(12,11)=2954,
W(12,12)=5026,
W(12,13)=9346,
W(12,14)=15956,
W(12,15)=29620,
W(12,16)=50726,
W(12,17)=94008,
W(12,18)=161464,

{12, 18, 32, 52, 96, 160, 298, 502, 936, 1586, 2954, 5026, 9346, 15956, 29620, 50726, 94008, 161464, 298752, 514548, 950586, 1641562, 3028184, 5242622, 9657426, 16760190, 30832418, 53632488, 98537132, 171781042}

2 LinearRecurrence[{2, 4, -9, -2, 9, -3}, {4, 6, 9, 16, 26, 48}, 30]