n*n网格沿格线划分成全等两部分的不同划分方案数目

mathe

刚才看到我女儿做的一道题目要求将4*4网格沿着格线划分成全等两部分，要求求出多个不等价的方案，所以想到这个问题。

wayne

貌似就是計算對稱中心位於n*n的網格的對稱軸上的, 中心對稱的路徑有多少條

hujunhua

4X4的规模对于小姑娘来说可能刚好合适。列举可能的分割线时遵循下述规则，可以减少遗漏和重复：
1、计数从起点到中心的路径即可。路径上无关于中心(0,0)对称的点。
2、路径不含边线，因为边线对于分割无贡献。
3、路径的起点位于网格的左边上部，显然不应包括角点，所以只有2个起点(-2,0)和(-2,1)。
4、除了起点，路径上不应再包含其它边界点。
5、不同路径的排序方法如下：从起点划线，直行者排在前，先拐弯者排在后。
答案应该是6种，见下图。

wayne

问题更加清晰了。根据楼上hujunhua的图说。
n*n的网格的不等价分割方案就是 1/4象限边缘的点（含一个边界点）到 中心 点的路径的条数之和。

而这个有点像是对$n/2$的整数划分。

zeroieme

开始列数列
1   （1*2）²   1
2   （2*2）²   6
3   （3*2）²  ？
4   （4*2）²  ？

边缘点到中心点的路径
然后怎么剔除非分割线？    不能同时经过180°对称的两点？

hujunhua

当规模更大时，3#的第 5 条排序方法需要细化：直行排前，先拐弯的排在后，拐弯时，向左(上)排前，向右(下)靠后。
按这个排序方法，不难编程计算。这样排出来的没有重复和遗漏。
以起点来分类，对每一个起点，每一条分割线都可以对应一个三进数。位数等于路径上的点数（不含起点），起点的下一点为最高位，以向下一点的方向配码，直行为0，左（上）拐为1，右（下）拐为2.

mathe

弄了个简单的穷举程序,可以计算到8*8(如果简单修改一下计算到10*10应该是可以的，但是在下去就不行了）。
然后可以搜索到
http://oeis.org/A113900

zeroieme

或者换成递归思路，(2n)²是附着在(2n-2)²外围的一层框分两半。

■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■

■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■

■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■

■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■

■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■

■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■

hujunhua

@zeroieme这种分层包围的递推方法我也想过，但是考虑的是增加了两圈点，处理起来不简单，不如上面考虑为一层框来得简明。

按照这种递归关系，由4X4生成6X6时，除了3#的第5图由于有对称轴只能生成10个外，其它5图应该可以生成19个，那么就是a(6)=5*19+10=105, 但是按OEIS上的A113900，a(6)却等于255。怎么会漏了这么多呢？

mathe

边界上可以进进出出的，中间不是简单的4*4