悠闲数学娱乐论坛(第2版)'s Archiver

青青子衿 发表于 2019-4-13 15:25

两个車的\(n\times\,n\)棋盘(旋转翻转等价)

一个\(\,n\times\,n\,\)棋盘放两个車,要求两个車既不同行也不同列。
算出在“旋转翻转等价”下的种类数
参见[url]http://kuing.orzweb.net/redirect.php?goto=findpost&ptid=3421&pid=30799[/url]
  1, 2, 3,  4,  5
  0, 1, 4, 13, 31

[url]https://en.wikipedia.org/wiki/Rook_polynomial[/url]

realnumber 发表于 2019-4-14 16:56

[i=s] 本帖最后由 realnumber 于 2019-4-15 09:33 编辑 [/i]

旋转翻转等价的话,
一个車的n×n 棋盘,
(1)若n为奇数,中心是1×1正方形,设为第1圈,环绕这个正方形的8格,设为第2圈,依次,最外围的是4n-4格的环,设为第0.5(n+1)圈.
从第一圈到第0.5(n+1)圈,放置种数和为1+2+...+0.5(n+1)=0.25(n+1)(0.5n+1.5).
(2)若n为偶数,中心是2×2正方形,设为第1圈,依次,最外围的是4n-4格的环,设为第0.5n圈.
从第一圈到第0.5n圈,放置种数和为1+2+...+0.5n=0.25n(0.5n+1).

二个車的n×n 棋盘,同样定义第k圈,记二个車分别在第x,y圈,此时放置种数为f(x.y),x≥y≥1.
注意到若其中一个車在正方体n×n 棋盘的轴对称方格上,那么另外一个車放置位置就会约少一半(与不在对称轴的格子比较),
(1)若n为奇数,轴对称的格子有米字四条
(2)若n为偶数,轴对称的格子有对角线两条
再对x,y取遍所有圈,f(x,y)累加即可.

-----没注意到不同行,不同列{:sweat:} ,错误留着吧.

Infinity 发表于 2019-4-14 21:38

声明一下,我理解的翻转是沿着与棋盘网格平行的两条对称轴进行的。当然也可使用对角线作为对称轴翻转,不过结果(数量)是否一样,未作分析。

可分而治之,采用递归策略。

棋盘中两条对称轴可将棋盘划分为四个等大的小棋盘,由于考虑旋转和翻转,因此两个車的分布情况无非就三种情况:a)在两个对称轴同侧;b)在两个对称轴的异侧;c)在某个对称轴同侧但在另一个对称轴异侧。于是可分别考虑:

a) 只要两个車在子棋盘中不同行且布同列即可,这就化不考虑旋转和翻转的简单问题了——当n为奇数时,两条对称轴通过格子,第一个棋子有$(n+1)^2/4$种落子方式,而第二个则有$(n+1)^2/4-n$种,故总共有$(n+1)^4/16-n(n+1)^2/4$种选择;当n为偶数时,对称轴只通过格线,故子棋盘为(n/2)×(n/2),类似分析可知两棋子总共有$n^2(n-2)^2/16$种分布。

b)此时由于位于异侧,所在的子棋盘整体是不同行不同列的,因此问题化为两个单独的一車落在子棋盘的问题,这种情况稍微复杂,跟n的奇偶性有关(因为n为奇数时棋子不能落在同一条对称轴上)。
若n为偶数,那么相当于两个独立的子棋盘在水平和竖直方向上整体错开放置。先不管旋转对称性,第一个車和第二个車的分配种数都是$(n/2)^2$种,故两車有$n^4/16$种分布。但注意,由中心对称与旋转等价可知,关于中心对称的两車分布只统计了一遍,而旋转后不重合的分布(即非中心对称分布)都被统计了两遍。偶数情形下,中心对称的分布种数等价为一个棋子在子棋盘放置的选择数,即$(n/2)^2$种,故减去后除以2就得到非中心对称的分布数。因此,偶数情况没有重复计数的两車总分布数为$n^4/32+n^2/8$种。

对于n为奇数情形,若两棋子都不在对称轴上,则可转化为更小规模的偶数情形的子问题(上面结果中n改为n-1)。对于剩下情形:i)只有一車落在对称轴上,ii)两車落在不同对称轴上则要小心处理。
i)此时由于旋转与中心对称等价,故可只考虑一車落在对称轴的半侧(包括中心)的情况。共有$n$种落子方案,而剩余一子则只能在另一个删除与对称轴重合的格子的子棋盘中的落子方案$(n-1)^2/4$种,故总共$n(n-1)^2/4$种方式。
ii)由于旋转等价性,只需考虑两个棋子落在两个直角边的情况即可。此时有$(n-1)^2/4$种分布方式。
因此n为奇数时共有$(n-1)^4/32+(n-1)^2(2n+3)/8$种分布方式。

c)此时相当于两个同样的子棋盘水平(或竖直)对齐排列,两个車分别在各自子棋盘上分布,只不过不能同行(或同列)。当n为偶数时,先不考虑对称翻折,第一个車有$(n/2)^2$种落子选择,而第二个車则不能同行(或同列),因此只有$n(n-2)/4$种选择,总共$n^3(n-2)/16$种选择。类似上面的分析,注意对称翻转后重合的分布不存在(因为不允许同行或同列),故所有符合要求的情形被统计了两次,即n为偶数时考虑翻转情形下两个車分布为$n^3(n-2)/32$种。
n为奇数时,两車落都不在对称轴上情况可转化为更小规模的偶数情形的子问题(n变为n-1),而棋子落在对称轴上的情况需要小心处理:包括i)只有一車落在对称轴上,ii)两車落在不同对称轴上。
i)由于翻折对称性,只需考虑一車落在直角边上,另一車落在一侧不含对称轴的子棋盘上即可。若落在属于边缘的对称轴上,有$(n+1)/2$种方式,剩余一子则在对面的子棋盘上有$(n-1)^2/4$种方式,共$(n-1)^2(n+1)/8$种;若落在子棋盘相邻边的那条对称轴上(除去与边缘对称轴的交点,即nxn棋盘的中心点),有$(n-1)/2$种,剩余一子则不能与之同行(或同列),有$(n-1)(n-3)/4$种,故两子落子方式有$(n-1)^2(n-3)/8$种,因此这种情形一共有$(n-1)^3/4$种落子方式。
ii)此时两子只能落在直角边且都不在直角边交点上,故有$(n-1)^2/4$种方式。
于是可知奇数情况一共有$(n-1)^3(n+5)/32+(n-1)^2/4$种方式。

综上,nxn棋盘考虑旋转和翻转,当n为奇数时,两車的落子方案有$(n-1)^2(2n^2+7n+9)/16$种;当n为偶数时,两車的落子方案有$n^2(2n^2-5n+6)/16$种。

青青子衿 发表于 2019-4-16 11:06

[i=s] 本帖最后由 青青子衿 于 2019-4-16 13:14 编辑 [/i]

[quote]综上,nxn棋盘考虑旋转和翻转,当n为奇数时,两車的落子方案有$(n-1)^2(2n^2+7n+9)/16$种;当n为偶数时,两車的落子方案有$n^2(2n^2-5n+6)/16$种。
[size=2][color=#999999]Infinity 发表于 2019-4-14 21:38[/color] [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30826&ptid=6019][img]http://kuing.orzweb.net/images/common/back.gif[/img][/url][/size][/quote]
可是,为什么我算出来的是这个呢?{:mad:}
\[a(n) =\begin{cases}\dfrac{1}{16}\bigg(4n(n-1)+n^2(n-1)^2+n^2\bigg) & n= 0\pmod2 \\
\dfrac{1}{16}\bigg(4n(n-1)+n^2(n-1)^2+(n-1)^2\bigg)& n= 1\pmod2\end{cases}\]
...[code]DiscretePlot[
Piecewise[{{(n (n^3 - 2 n^2 + 6 n - 4))/16, Mod[n, 2] == 0},
   {((n - 1) (n^3 - n^2 + 5 n - 1))/16, Mod[n, 2] == 1}}],{n, 20}][/code]...
\[\color{black}{a(n) =\begin{cases}\dfrac{1}{16}n\bigg(n^3-2n^2+6n-4\bigg) & n= 0\pmod2 \\
\dfrac{1}{16}\big(n-1\big)\bigg(n^3-n^2+5n-1\bigg)& n= 1\pmod2\end{cases}}\]

Infinity 发表于 2019-4-16 13:05

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30832&ptid=6019]4#[/url] [i]青青子衿[/i] [/b]
我也不保证自己计算是否有遗漏。你可以把你的计算过程写下来,不然没法判断问题在哪呀。

kuing 发表于 2019-4-16 15:03

[quote]声明一下,我理解的翻转是沿着与棋盘网格平行的两条对称轴进行的。当然也可使用对角线作为对称轴翻转,不过结果(数量)是否一样,未作分析。 ...
[size=2][color=#999999]Infinity 发表于 2019-4-14 21:38[/color] [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30826&ptid=6019][img]http://kuing.orzweb.net/images/common/back.gif[/img][/url][/size][/quote]
你理解的翻转与旋转的复合就可以得出对角线翻转。
比如:逆时针旋转 90 度 * 左右翻转 = 沿 y=x 翻转;顺时针旋转 90 度 * 左右翻转 = 沿 y=n-x 翻转。
所以旋转及左右翻转等价实际上已经包含了对角线翻转等价。

Infinity 发表于 2019-4-16 18:32

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30840&ptid=6019]6#[/url] [i]kuing[/i] [/b]
对哦,也可以这样复合,那么就是等价的了。这样说来,上面给出的结果就不对了,因为我没有考虑对角线对称的问题。

kuing 发表于 2019-4-16 18:45

照抄前些天的这帖 [url]http://kuing.orzweb.net/redirect.php?goto=findpost&ptid=5979&pid=30608[/url] 好了

记 `\{f_1,f_2,\ldots,f_8\}` 分别表示 `\{`不动,旋转90度,旋转180度,旋转270度,上下翻转,左右翻转,左上至右下翻转,左下至右上翻转`\}`,这是一个置换群,然后计算各 `f_i` 作用下不变的放車数。

先计算 `n` 为偶数时,`f_1` 的自然是满足不同行不同列的全部,易知为 `n^2(n-1)^2/2`;

对于 `f_2`,要使旋转 90 度后不变,由于只有两只車,这显然是不存在的,`f_4` 也是;

对于 `f_3`,即是要两只車中心对称,易知是 `n^2/2`;

对于 `f_5`,由于偶数,上下翻转不变则必在同一列,不符合条件,`f_6` 也是;

对于 `f_7`,即是要两只車关于对角线对称,两种情况,一是不在对角线上的,有 `(n^2-n)/2`,另一是在对角线上任取,有 `C_n^2`,所以共 `n^2-n`,对 `f_8` 同理。

综上,由 Burnside 引理得结果就是
\[\frac{n^2(n-1)^2/2+n^2/2+(n^2-n)\cdot2}8=\frac1{16}n(n^3-2n^2+6n-4);\]

再计算 `n` 为奇数时,`f_1` 同样是 `n^2(n-1)^2/2`,`f_2`, `f_4` 同样不存在;

对于 `f_3`,即是要两只車中心对称且不在两中线上,易知是 `(n-1)^2/2`;

对于 `f_5`,上下翻转不变就只能都在水平中线上,还是不符合条件,`f_6` 也是;

`f_7`, `f_8` 和偶数时一样。

综上,由 Burnside 引理得结果就是
\[\frac{n^2(n-1)^2/2+(n-1)^2/2+(n^2-n)\cdot2}8=\frac1{16}(n-1)(n^3-n^2+5n-1).\]

结果和纸巾的一样。

PS、为啥你的代码到处都是 \, [precode]\(\,n\times\,n\,\)[/precode]…………

青青子衿 发表于 2019-4-16 19:46

[quote]照抄前些天的这帖 ...
[size=2][color=#999999]kuing 发表于 2019-4-16 18:45[/color] [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30847&ptid=6019][img]http://kuing.orzweb.net/images/common/back.gif[/img][/url][/size][/quote]
KK是真的强{:victory:}
[quote]结果和纸巾的一样。
PS、为啥你的代码到处都是 \, [precode]\(\,n\times\,n\,\)[/precode]…………
[size=2][color=#999999]kuing 发表于 2019-4-16 18:45[/color] [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30847&ptid=6019][img]http://kuing.orzweb.net/images/common/back.gif[/img][/url][/size][/quote]
是这样的……LaTeX代码中,打一些以字母结尾的命令时,总是会因为与后面的字母黏在一起而报错所以就养成了一个奇怪的习惯(加逗号)

Infinity 发表于 2019-4-16 19:58

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30847&ptid=6019]8#[/url] [i]kuing[/i] [/b]
如果变成三个或是更多的情况怎么分析?感觉Burnside引理在棋子数(或者染色数)比较少的情况下还可以用,对于比较大的情形一般用Polya定理,但对于它对于约束的解决比较麻烦。

另外,请问一下aabb填入4×4方格那个问题考虑旋转翻转时用该方法怎么解决?

kuing 发表于 2019-4-17 01:27

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30849&ptid=6019]10#[/url] [i]Infinity[/i] [/b]

试了一下同类的三和四,三还好点,四已经有点难。

同类的三只車:
\begin{align*}
f_1\colon &&& \frac{n^2(n-1)^2(n-2)^2}{3!}, \\
f_3\colon &&& \led & 0, && n=2k, \\ & \frac{(n-1)^2}2, && n=2k+1, \endled\\
f_7,f_8\colon &&& \frac{n(n-1)}2\cdot(n-2)+C_n^3,
\end{align*}综上,当 `n` 为偶数时
\begin{align*}
N_3&=\frac18\left( \frac{n^2(n-1)^2(n-2)^2}{3!}+n(n-1)(n-2)+2C_n^3 \right)\\
&=\frac1{48}n(n-1)(n-2)(n^3-3n^2+2n+8);
\end{align*}当 `n` 为奇数时
\begin{align*}
N_3&=\frac18\left( \frac{n^2(n-1)^2(n-2)^2}{3!}+\frac{(n-1)^2}2+n(n-1)(n-2)+2C_n^3 \right)\\
&=\frac1{48}(n^2-1)(n^4-6n^3+14n^2-10n-3).
\end{align*}

同类的四只車:
\begin{align*}
f_1\colon &&& \frac{n^2(n-1)^2(n-2)^2(n-3)^2}{4!}, \\
f_2,f_4\colon &&& \led & \frac{n^2-2n}4, && n=2k, \\ & \frac{n^2-4n+3}4, && n=2k+1, \endled\\
f_3\colon &&& \led & \frac{n^2(n-2)^2}8, && n=2k, \\ & \frac{(n-1)^2(n-3)^2}8, && n=2k+1, \endled\\
f_7,f_8\colon &&& \frac{n(n-1)(n-2)(n-3)}8+\frac{n(n-1)}2C_{n-2}^2+C_n^4,
\end{align*}综上,当 `n` 为偶数时
\begin{align*}
N_4={}&\frac18\biggl( \frac{n^2(n-1)^2(n-2)^2(n-3)^2}{4!}+\frac{n^2-2n}2+\frac{n^2(n-2)^2}8\\
&+\frac{n(n-1)(n-2)(n-3)}4+n(n-1)C_{n-2}^2+2C_n^4 \biggr)\\
={}&\frac1{192}n(n-2)(n^6-10n^5+38n^4-68n^3+80n^2-104n+72);
\end{align*}当 `n` 为奇数时
\begin{align*}
N_4={}&\frac18\biggl( \frac{n^2(n-1)^2(n-2)^2(n-3)^2}{4!}+\frac{n^2-4n+3}2+\frac{(n-1)^2(n-3)^2}8\\
&+\frac{n(n-1)(n-2)(n-3)}4+n(n-1)C_{n-2}^2+2C_n^4 \biggr)\\
={}&\frac1{192}(n-1)(n-3)(n^6-8n^5+23n^4-28n^3+35n^2-52n+21).
\end{align*}

按照以上公式,有:
`3\times3` 放三只車有 `2` 种;
`4\times4` 放三只車有 `16` 种;
`4\times4` 放四只車有 `7` 种;
`5\times5` 放四只車有 `89` 种;
是否正确,其实我也没什么把握,要是有程序验证一下就好了,可是不知怎么编,谁有办法?

枚举的话,3*3-三应该没问题,4*4-四的话,我已经列了如下 7 种:
[attach]7162[/attach]
如果还有的话,那就是我错了……其他情况实在不好枚举……

青青子衿 发表于 2019-4-17 07:41

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30855&ptid=6019]11#[/url] [i]kuing[/i] [/b]
kk,睡得真晚~

[quote]是否正确,其实我也没什么把握,要是有程序验证一下就好了,可是不知怎么编,谁有办法?
[size=2][color=#999999]kuing 发表于 2019-4-17 01:27[/color] [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30855&ptid=6019][img]http://kuing.orzweb.net/images/common/back.gif[/img][/url][/size][/quote]
4*4的棋盘放四个既不同行也不同列的車,之前玩过
参见:[url]https://bbs.emath.ac.cn/thread-5375-1-1.html[/url]

[b](发现Oeis上收录的序列是:n×n的棋盘放n个既不同行也不同列的車;
目前为止,并没有收录:n×n的棋盘放2个既不同行也不同列的車)[/b]

考虑每行每列有且仅有一个\(\,1\,\)的\(\,4\times4\,\)二进制方阵;
若考虑[b]旋转等价[/b]([url]http://oeis.org/A263685[/url]),那么这样的二进制方阵有9个:
\begin{align*}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}\\
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\end{align*}
,,,[code]e = Identity;
f = Reverse;
g = Transpose;
Grot = {e, f@*g, g@*f, f@*g@*f@*g};
MatrixPlot[#, ImageSize -> Tiny, ColorFunction -> "Monochrome"] & /@
DeleteDuplicates[
  SparseArray@Thread[Transpose[{Range[4], #}] -> 1] & /@
   Permutations@Range[4], MemberQ[Through@Grot[#1], #2] &]
[/code]...

若考虑[b]旋转翻转等价[/b]([url]http://oeis.org/A000903[/url]),那么这样的二进制方阵有7个:
\begin{align*}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\\
&&
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
&&
\overset{\Large\overset{\huge\overset{\huge{\square}}{\blacksquare}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\square}}{\blacksquare}
\overset{\Large\overset{\huge\overset{\huge{\blacksquare}}{\square}}{\square}}{\square}
\overset{\Large\overset{\huge\overset{\huge{\square}}{\square}}{\blacksquare}}{\square}
\end{align*}
,,,[code]e = Identity;
f = Reverse;
g = Transpose;
Grotflip = {e, f, g, f@*g, g@*f, f@*g@*f, g@*f@*g, f@*g@*f@*g};
MatrixPlot[#, ImageSize -> Tiny, ColorFunction -> "Monochrome"] & /@
DeleteDuplicates[
  SparseArray@Thread[Transpose[{Range[4], #}] -> 1] & /@
   Permutations@Range[4], MemberQ[Through@Grotflip[#1], #2] &][/code]...

kuing 发表于 2019-4-17 13:57

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30856&ptid=6019]12#[/url] [i]青青子衿[/i] [/b]

程序看不懂{:sad:}
有没有 4*4 放三个或 5*5 放四个的?

Infinity 发表于 2019-4-17 14:51

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30855&ptid=6019]11#[/url] [i]kuing[/i] [/b]
仿照12楼可编写如下程序验证nxn棋盘,k个車的分布种数[code]e = Identity; f = Reverse; g = Transpose;
Grot = {e, f@*g, g@*f, f@*g@*f@*g};
Grotflip = {e, f, g, f@*g, g@*f, f@*g@*f, g@*f@*g, f@*g@*f@*g};
n = 4; k = 3;
s = SparseArray[#, {n,
      n}] & /@ (Table[# ->
         1 & /@ (Transpose@{Subsets[Range[n], {k}][[i]],
          Permutations[Range[n], {k}][[j]]}), {i, 1,
       Binomial[n, k]}, {j, 1, FactorialPower[n, k]}] //
     Flatten[#, 1] &);
MatrixPlot[#, ColorRules -> {1 -> RGBColor[1, .75, .5]},
   ImageSize -> Tiny, Mesh -> All, Frame -> None,
   FrameTicks -> None] & /@
DeleteDuplicates[s, MemberQ[Through@Grotflip[#1], #2] &]
% // Length[/code][attach]7164[/attach]

kuing 发表于 2019-4-17 14:55

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30864&ptid=6019]14#[/url] [i]Infinity[/i] [/b]

多谢!very nice!

青青子衿 发表于 2019-4-17 17:43

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30864&ptid=6019]14#[/url] [i]Infinity[/i] [/b]
那个MMA程序改进得相当好!赞一个!
\begin{align*}
N(2,n)&=\begin{cases}\dfrac{1}{16}n\bigg(n^3-2n^2+6n-4\bigg) & n= 0\pmod2 \\  
\dfrac{1}{16}\big(n-1\big)\bigg(n^3-n^2+5n-1\bigg)& n= 1\pmod2\end{cases}\\
N(3,n)&=\begin{cases}\dfrac{1}{48}n\big(n-1\big)\big(n-2\big)\bigg(n^3-3n^2+2n+8\bigg) & n= 0\pmod2 \\  
\dfrac{1}{48}\big(n^2-1\big)\bigg(n^4-6n^3+14n^2-10n-3\bigg) & n= 1\pmod2\end{cases}\\
N(4,n)&=\begin{cases}\dfrac{1}{192}n\big(n-2\big)\bigg(n^6-10n^5+38n^4-68n^3+80n^2-104n+72\bigg) & n= 0\pmod2 \\  
\dfrac{1}{192}\big(n-1\big)\big(n-3\big)\bigg(n^6-8n^5+23n^4-28n^3+35n^2-52n+21\bigg) & n= 1\pmod2\end{cases}\\
\end{align*}[code]Table[Piecewise[{
   {(n (n^3 - 2 n^2 + 6 n - 4))/16, Mod[n, 2] == 0},
   {((n - 1) (n^3 - n^2 + 5 n - 1))/16, Mod[n, 2] == 1}
   }], {n, 20}]
Table[Piecewise[{
   {(n (n - 1) (n - 2) (n^3 - 3 n^2 + 2 n + 8))/48, Mod[n, 2] == 0},
   {((n^2 - 1) (n^4 - 6 n^3 + 14 n^2 - 10 n - 3))/48, Mod[n, 2] == 1}
   }], {n, 20}]
Table[Piecewise[{
   {(n (n - 2) (n^6 - 10 n^5 + 38 n^4 - 68 n^3 + 80 n^2 - 104 n + 72))/192,
          Mod[n, 2] == 0},
   {((n - 1) (n - 3) (n^6 - 8 n^5 + 23 n^4 - 28 n^3 + 35 n^2 - 52 n + 21))/192,
         Mod[n, 2] == 1}
   }], {n, 20}][/code]...
\begin{align*}
N(5,n)&=\begin{cases}\dfrac{1}{960}n\big(n-1\big)\big(n-2\big)\big(n-3\big)\big(n-4\big)\bigg(n^5-10n^4+35n^3-50n^2+24n+52\bigg) & n= 0\pmod2 \\   
\dfrac{1}{960}\big(n-1\big)\big(n-3\big)\bigg(n^8-16n^7+103n^6-340n^5+604n^4-492n^3-105n^2+356n+105\bigg) & n= 1\pmod2\end{cases}\\
\end{align*}
,,,[code]Table[Piecewise[{
   {(n (n - 1) (n - 2) (n - 3) (n - 4)
         (n^5 - 10 n^4 + 35 n^3 - 50 n^2 + 24 n + 52))/960,
         Mod[n, 2] == 0},
   {((n - 1) (n - 3)
        (n^8 - 16 n^7 + 103 n^6 - 340 n^5 + 604 n^4
         - 492 n^3 - 105 n^2 + 356 n + 105))/960,
        Mod[n, 2] == 1}
   }], {n, 20}][/code]

kuing 发表于 2019-4-17 18:18

同类的五只車,比四只还简单些:
\begin{align*}
f_1\colon &&& \frac{n^2(n-1)^2(n-2)^2(n-3)^2(n-4)^2}{5!}, \\
f_2,f_4\colon &&& \led & 0, && n=2k, \\ & \frac{n^2-4n+3}4, && n=2k+1, \endled\\
f_3\colon &&& \led & 0, && n=2k, \\ & \frac{(n-1)^2(n-3)^2}8, && n=2k+1, \endled\\
f_7,f_8\colon &&& \frac{n(n-1)(n-2)(n-3)}8C_{n-4}^1+\frac{n(n-1)}2C_{n-2}^3+C_n^5,
\end{align*}综上,当 $n$ 为偶数时
\begin{align*}
N_5={}&\frac18\biggl( \frac{n^2(n-1)^2(n-2)^2(n-3)^2(n-4)^2}{5!}\\
&+\frac{n(n-1)(n-2)(n-3)}4C_{n-4}^1+n(n-1)C_{n-2}^3+2C_n^5 \biggr)\\
={}&\frac1{960}n(n-1)(n-2)(n-3)(n-4)(n^5-10n^4+35n^3-50n^2+24n+52);
\end{align*}当 $n$ 为奇数时
\begin{align*}
N_5={}&\frac18\biggl( \frac{n^2(n-1)^2(n-2)^2(n-3)^2(n-4)^2}{5!}+\frac{n^2-4n+3}2+\frac{(n-1)^2(n-3)^2}8\\
&+\frac{n(n-1)(n-2)(n-3)}4C_{n-4}^1+n(n-1)C_{n-2}^3+2C_n^5 \biggr)\\
={}&\frac1{960}(n-1)(n-3)(n^8-16n^7+103n^6-340n^5+604n^4-492n^3-105n^2+356n+105).
\end{align*}

`N_3` 取 `n` 由 3~10 为 {[color=Red]2, 16, 86, 320, 956[/color], 2408, 5380, 10920}
`N_4` 取 `n` 由 4~10 为 {[color=Red]7, 89, 723, 3773[/color], 14914, 47982, 132930}
`N_5` 取 `n` 由 5~10 为 {[color=Red]23, 579[/color], 6762, 47404, 238998, 954198}
其中红色的数字已通过 14# 的程序验证,其中 `N_4` 的 3773 跑了差不多两小时{:sweat:}所以也不敢去跑下面的 6762 了……

Infinity 发表于 2019-4-17 19:45

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30873&ptid=6019]17#[/url] [i]kuing[/i] [/b]
当n增大时,矩阵变得很大,相应不考虑旋转和翻转的布子结果增加很多,从而需要删除重复的比对过程非常慢。
由于结果是多项式,因为高次多项式振荡趋势比较强,所以对结果很敏感,只要有一两个对就说明不会错。相应地,低次多项式则需要多验证才行,因为变化平滑,容易出现部分结果符合而后面不符合。
相信你的计算没问题。我们可以验证中间结果(比如f1,f2,f3,f7)来减少计算量。
比如下面代码可验证顺时针180旋转的不动点个数(17楼中的f3)[code]n = 7; k = 5;
s = SparseArray[#, {n,
     n}] & /@ (Table[# ->
        1 & /@ (Transpose@{Subsets[Range[n], {k}][[i]],
         Permutations[Range[n], {k}][[j]]}), {i, 1,
      Binomial[n, k]}, {j, 1, FactorialPower[n, k]}] //
    Flatten[#, 1] &);
Select[s, SameQ[f@*g@*f@*g@#, #] &]//Length[/code]

kuing 发表于 2019-4-17 21:34

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30875&ptid=6019]18#[/url] [i]Infinity[/i] [/b]

谢谢!
这个程序我大概能看懂,验证其他的就改最后一行
{e, f, g, f@*g, g@*f, f@*g@*f, g@*f@*g, f@*g@*f@*g}
分别代表我的
{f1, f5, f8, f2, f4, f7, f6, f3}

业余的业余 发表于 2019-4-18 03:28

[quote]同类的五只車,比四只还简单些:
\begin{align*}
f_1\colon &&& \frac{n^2(n-1)^2(n-2)^2(n-3)^2(n-4)^2}{5 ...
[size=2][color=#999999]kuing 发表于 2019-4-17 18:18[/color] [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30873&ptid=6019][img]http://kuing.orzweb.net/images/common/back.gif[/img][/url][/size][/quote]
$N_5$ 后面的数字都验证无误。 接下来的 $11_5=3204768$.

色k 发表于 2019-4-18 08:46

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30886&ptid=6019]20#[/url] [i]业余的业余[/i] [/b]

{:shocked:}你用什么方法验证的呀?

业余的业余 发表于 2019-4-18 13:14

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30891&ptid=6019]21#[/url] [i]色k[/i] [/b]

写了个C++ 程序,比 mma 费事,效率也好些。不过后面也要跑近十分钟了。

kuing 发表于 2019-4-18 22:42

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30896&ptid=6019]22#[/url] [i]业余的业余[/i] [/b]

那已经快很多了!那能不能再帮我验证一下下面这个表的数据是否正确{:lol:}

`n\times n` 放同类的 `m` 只車的数目记为 `N(m,n)`,有:
N(6,n) 的 n 取 6~10 为:{115, 4549, 71188, 636732, 3973590}
N(7,n) 的 n 取 7~11 为:{694, 40784, 818664, 9078960, 68626740}
N(8,n) 的 n 取 8~12 为:{5282, 410010, 10215810, 137246730, 1235031390}
N(9,n) 的 n 取 9~13 为:{46066, 4542550, 137251240, 2195568100, 23189645170}
N(10,n) 的 n 取 10~14 为:{456454, 54912194, 1976055564, 37103361844, 454510241654}

如果都正确,那我刚才推出的一般公式看来就没问题了{:lol:}

业余的业余 发表于 2019-4-19 03:40

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30904&ptid=6019]23#[/url] [i]kuing[/i] [/b]

$m=6$ 时通过,
$m=7 \text{到}10$时,验证到$n=10$ 都通过。

对 $m=10$ 试 $n=11$ 时 内存溢出。因是验证目的,不敢优化,要存储各个不同的棋盘排子状态的。

我觉得已经可以确定公式的正确性了,其实验证连续 $4$ 个 $m$ 就已经很保险了,涉及到的旋转 $90\du$, $180\du$, 镜面,镜面后旋转 $90\du$, $180\du$ 的各种子情形都测试到了。

kuing 发表于 2019-4-19 09:56

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30909&ptid=6019]24#[/url] [i]业余的业余[/i] [/b]

谢谢,那我就放心发了{:lol:}

同类 `m`(`m\geqslant2`)只車的一般公式。

为方便书写用 `O`, `J` 表示偶数集和奇数集。

首先 `f_1` 恒为 `n^2(n-1)^2(n-2)^2\cdots(n-m+1)^2/m!`,或者换个更好看的写法,即
\[f_1\colon\quad m!(C_n^m)^2. \quad(*)\]

然后是 `f_2` 和 `f_4`,当 `n\in O`,显然必须 `m=4p` 时才存在,每次放四只循环对称的車,第一次有 `n/2(n/2-1)` 种选择,第二次就剩下 `(n/2-2)(n/2-3)`,如此类推,最后再除以它们的全排列,即
\[\frac n2\left( \frac n2-1 \right)\left( \frac n2-2 \right)\left( \frac n2-3 \right)\cdots\left( \frac n2-2p+2 \right)\left( \frac n2-2p+1 \right)\frac1{p!},\]
化简为 `C_{n/2}^{2p}C_{2p}^pp!`,类似地,当 `n\in J`,必须 `m=4p` 或 `4p+1` 时才存在,结果为 `C_{[n/2]}^{2p}C_{2p}^pp!`,即
\[
f_2,f_4\colon\quad \led
&C_{n/2}^{2p}C_{2p}^pp!, && n\in O\land m=4p,\\
&C_{[n/2]}^{2p}C_{2p}^pp!, && n\in J\land(m=4p\lor m=4p+1),
\endled
\]
注意两式可以合而为一,即
\[f_2,f_4\colon\quad C_{[n/2]}^{[m/2]}C_{[m/2]}^{[m/4]}[m/4]!, \quad m=4p\lor(n\in J\land m=4p+1), \quad(**)\]

接下来的我就不详细解释了,道理差不多,直接写结果。

`f_3` 的:当 `n\in O`,必须 `m=2p` 时才存在,为 `n^2(n-2)^2(n-4)^2\cdots(n-2p+2)^2/(2^pp!)`,化简为 `(C_{n/2}^p)^22^pp!`,类似地,当 `n\in J`,则 `m=2p` 或 `2p+1` 时,结果都为 `(C_{[n/2]}^p)^22^pp!`,即
\[
f_3\colon\quad \led
&(C_{n/2}^p)^22^pp!, && n\in O\land m=2p,\\
&(C_{[n/2]}^p)^22^pp!, && n\in J\land(m=2p\lor m=2p+1),
\endled
\]
两式同样可以合而为一,即
\[f_3\colon\quad (C_{[n/2]}^{[m/2]})^22^{[m/2]}[m/2]!, \quad \lnot(n\in O\land m\in J), \quad(*{*}*)\]

`f_7`, `f_8` 的:当有 `2k` 只車不在对角线上时,有 `C_{n-2k}^{m-2k}\cdot n(n-1)(n-2)\cdots(n-2k+1)/(2^kk!)` 种选择,化简为 `C_n^mC_m^{2k}(2k-1)!!`(这是双阶乘,表示 `(2k-1)(2k-3)(2k-5)\cdots`,且此处规定 `(-1)!!=1`),所以
\[f_7,f_8\colon\quad C_n^m\sum_{k=0}^{[m/2]}C_m^{2k}(2k-1)!!.\quad(*{**}*)\]

那么,记
\begin{align*}
A&=m!(C_n^m)^2+2C_n^m\sum_{k=0}^{[m/2]}C_m^{2k}(2k-1)!!,\\
B&=2C_{[n/2]}^{[m/2]}C_{[m/2]}^{[m/4]}[m/4]!,\\
C&=(C_{[n/2]}^{[m/2]})^22^{[m/2]}[m/2]!,
\end{align*}
则综上所述,有
\[
N(m,n)=
\led
& \frac A8, && n\in O\land m\in J,\\
& \frac{A+C}8, && (n\in O\land m\bmod4=2)\lor(n\in J\land m\bmod4\geqslant2),\\
& \frac{A+B+C}8, && (n\in O\land m\bmod4=0)\lor(n\in J\land m\bmod4<2),
\endled
\]
这就是一般公式。

(或许你会问为啥 `m=1` 不符合此公式,这是因为 `m=1` 且 `n\in J` 时 `f_5`, `f_6` 都存在,且个数都为 `n`,所以其实补上去也行的,不过显然没必要)

kuing 发表于 2019-4-19 10:33

根据此公式用 MMC(A) 列出那些数字:[code]AA[m_, n_] := m! Binomial[n, m]^2 + 2 Binomial[n, m] Sum[Binomial[m, 2 k] (2 k - 1)!!, {k, 0, Floor[m/2]}]
BB[m_, n_] := 2 Binomial[Floor[n/2], Floor[m/2]] Binomial[Floor[m/2], Floor[m/4]] Floor[m/4]!
CC[m_, n_] := Binomial[Floor[n/2], Floor[m/2]]^2*2^(Floor[m/2]) Floor[m/2]!
NN[m_, n_] := If[EvenQ[n] && OddQ[m], AA[m, n]/8,
If[EvenQ[n] && (Mod[m, 4] == 2) || OddQ[n] && (Mod[m, 4] >= 2), (AA[m, n] + CC[m, n])/8,
If[EvenQ[n] && (Mod[m, 4] == 0) || OddQ[n] && (Mod[m, 4] < 2), (AA[m, n] + BB[m, n] + CC[m, n])/8]]]
Table[NN[i, j], {i, 2, 11}, {j, i, i + 5}] // MatrixForm[/code]输出:
\[\left(
\begin{array}{cccccc}
1 & 4 & 13 & 31 & 66 & 123 \\
2 & 16 & 86 & 320 & 956 & 2408 \\
7 & 89 & 723 & 3773 & 14914 & 47982 \\
23 & 579 & 6762 & 47404 & 238998 & 954198 \\
115 & 4549 & 71188 & 636732 & 3973590 & 19219338 \\
694 & 40784 & 818664 & 9078960 & 68626740 & 395222256 \\
5282 & 410010 & 10215810 & 137246730 & 1235031390 & 8348356422 \\
46066 & 4542550 & 137251240 & 2195568100 & 23189645170 & 181804372750 \\
456454 & 54912194 & 1976055564 & 37103361844 & 454510241654 & 4090576223202 \\
4999004 & 718609488 & 30357439752 & 661105289936 & 9296759852940 & 95198732970432 \\
\end{array}
\right)\]

Infinity 发表于 2019-4-19 14:05

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30878&ptid=6019]19#[/url] [i]kuing[/i] [/b]
是的。上面的代码也是全局排除法找到某个置换下的不变布子方案。

其实按照17楼结果不难写出考虑旋转和翻转情况下,$n\times n$棋盘中任意`m(m\leqslant n)`个車的的分布方案数:
当$n$为奇数时\[f_1=m!(C_n^m)^2\]\[f_2,f_4=\begin{cases}\frac{A_{\frac{n-1}{2}}^{\frac m2}}{(\frac m4)!},&&m\equiv0\pmod 4\\&&
\\\frac{A_{\frac{n-1}{2}}^{\frac {m-1}2}}{(\frac {m-1}4)!},&&m\equiv1\pmod 4\\&&
\\ 0,&&m\equiv2,3\pmod 4\end{cases}\quad
f_3=\begin{cases}\frac{2^{\frac m2}\left(A_{\frac{n-1}{2}}^{\frac m2}\right)^2}{(\frac m2)!},&&m\equiv0\pmod 2\\
&&\\ \frac{2^{\frac {m-1}2}\left(A_{\frac{n-1}{2}}^{\frac {m-1}2}\right)^2}{(\frac {m-1}2)!},&&m\equiv1\pmod 2\end{cases}\]
\[f_5,f_6=0\]
\[f_7,f_8=\begin{cases}\sum_{k=0}^{\frac m2}\frac{A_n^{2k}}{2^kk!}C_{n-2k}^{m-2k},&&m\equiv 0\pmod 2\\&&
\\\sum_{k=0}^{\frac{m-1}2}\frac{A_n^{2k}}{2^kk!}C_{n-2k}^{m-2k},&&m\equiv 1\pmod 2\end{cases}\]
当$n$为偶数时\[f_1=m!(C_n^m)^2\]\[f_2,f_4=\begin{cases}\frac{A_{\frac n2}^{\frac m2}}{(\frac m4)!},&&m\equiv0\pmod 4\\&&
\\0,&&m\equiv1\pmod 4\\&&
\\ 0,&&m\equiv2,3\pmod 4\end{cases}\quad
f_3=\begin{cases}\frac{2^{\frac m2}\left(A_{\frac n 2}^{\frac m2}\right)^2}{(\frac m2)!},&&m\equiv0\pmod 2\\
&&\\ 0,&&m\equiv1\pmod 2\end{cases}\]
\[f_7,f_8=\begin{cases}\sum_{k=0}^{\frac m2}\frac{A_n^{2k}}{2^kk!}C_{n-2k}^{m-2k},&&m\equiv 0\pmod 2\\&&
\\\sum_{k=0}^{\frac{m-1}2}\frac{A_n^{2k}}{2^kk!}C_{n-2k}^{m-2k},&&m\equiv 1\pmod 2\end{cases}\]
然后通过代码来进行验证,m较大的情形更有验证的价值,不过此时n必须大于等于m,故m和n都比较大,此时即使采用18#代码,恐怕也很费时间,考虑到每种置换中一定存在某几类布子方案一定不符合要求。比如,对于f2情形,除了不同行同列之外,棋子必然不能分布在对角线上,也不能存在任何两子所在行列相交于对角线上一点——只有满足这些要求的才能参与排除重复过程,否则必然会出现整个棋盘存在同行或同列棋子冲突的情况。好处就是将n和m的规模降低了一半,此时效率理论上能提高不少。

kuing 发表于 2019-4-19 14:33

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30913&ptid=6019]27#[/url] [i]Infinity[/i] [/b]

一般结果 25# 已经写了,我还做了一些化简,都化成 C 了(我比较喜欢用 C{:lol:}),而且利用取整函数将式子尽可能合一,这样比较好看。
至于编程方面,我玩得少,只会最简单的……道理虽然能理解,也不知具体怎么实现……

kuing 发表于 2019-4-19 14:52

同类車都费了那么多神,aabb 啥的暂时不敢碰了{:lol:}得换换口味,有空再回来玩……

Infinity 发表于 2019-4-19 15:26

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30914&ptid=6019]28#[/url] [i]kuing[/i] [/b]
我这几天有事没注意帖子更新了回复,今天直接回复后才发现你已经弄了。本来我也想直接用取整函数的,能统一表达,只是那样的解析性质不太好(不利于分析),所以又改回来了。

程序我待会儿发出来。

青青子衿 发表于 2019-4-19 16:21

楼上的答复都太精彩了{:lol:}
\begin{array}{|c|c|c|c|}
\hline
&
N\left(\,2\,,\,*\,\right)&N\left(\,3\,,\,*\,\right)&
N\left(\,4\,,\,*\,\right)&N\left(\,5\,,\,*\,\right)&
N\left(\,6\,,\,*\,\right)&N\left(\,7\,,\,*\,\right)\\
\hline
N\left(\,*\,,\,2\,\right)
&1&4&13&31&66&123\\
\hline
N\left(\,*\,,\,3\,\right)&
&2&16&86&320&956\\
\hline
N\left(\,*\,,\,4\,\right)&&
&7&89&723&3773\\
\hline
N\left(\,*\,,\,5\,\right)&&&
&23&579&6762\\
\hline
N\left(\,*\,,\,6\,\right)&&&&
&115&4549\\
\hline
N\left(\,*\,,\,7\,\right)&&&&&
&694\\
\hline
\end{array}

kuing 发表于 2019-4-19 17:08

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30916&ptid=6019]30#[/url] [i]Infinity[/i] [/b]

嗯,说得有道理,好看未必好用{:lol:}

另一种写法:
\begin{align*}
&N(m=2p+1,n=2q)\\
={}&\frac18\left( m!(C_n^m)^2+2C_n^m\sum_{k=0}^pC_m^{2k}(2k-1)!! \right),\\
&N(m=4p+2,n=2q),\ N(m=4p+\{2,3\},n=2q+1)\\
={}&\frac18\left( m!(C_n^m)^2+2C_n^m\sum_{k=0}^{2p+1}C_m^{2k}(2k-1)!!+(C_q^{2p+1})^22^{2p+1}(2p+1)! \right),\\
&N(m=4p,n=2q),\ N(m=4p+\{0,1\},n=2q+1)\\
={}&\frac18\left( m!(C_n^m)^2+2C_n^m\sum_{k=0}^{2p}C_m^{2k}(2k-1)!!+2C_q^{2p}C_{2p}^pp!+(C_q^{2p})^22^{2p}(2p)! \right),
\end{align*}
当然也可以逐条详细写出,不过懒了……

Infinity 发表于 2019-4-19 17:14

其实MMA是函数式编程,如果采用这种风格,将会"智能地"按照函数定义规则去执行,这一过程非常符合人类的数学逻辑过程,编写起来也非常流畅。
由于只计算数字结果,所以可以将27楼结果相应用取整函数替代各种模剩余类后,按照函数式编程如下:[code]f1[n_, m_] := m! Binomial[n, m]^2;
f24[n_?OddQ, m_ /; Mod[m, 4] >= 2] = 0;
f24[n_?EvenQ, m_ /; Mod[m, 4] > 0] = 0;
f24[n_, m_] := FactorialPower[Floor[n/2], Floor[m/2]]/Floor[m/4]!
f3[n_?EvenQ, m_?OddQ] = 0;
f3[n_, m_] :=
  2^Floor[m/2] FactorialPower[Floor[n/2], Floor[m/2]]^2/Floor[m/2]!;
f78[n_, m_] :=
  Sum[FactorialPower[n, 2 k] Binomial[n - 2 k, m - 2 k]/(2^k k!), {k,
    0, Floor[m/2]}];
Chess[n_Integer?Positive,
   m_Integer?
    Positive] := (f1[n, m] + 2 f24[n, m] + f3[n, m] + 2 f78[n, m])/8;
Table[Chess[n, m], {m, 2, 11}, {n, m, m + 5}][/code]返回结果跟26楼一样。
当然,像31楼那样的上对角矩阵使得行列意义更加明显:[code]Table[If[i <= j, Chess[j, i], 0], {i, 2, 11}, {j, 2, 11}][/code]

Infinity 发表于 2019-4-19 17:37

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30918&ptid=6019]32#[/url] [i]kuing[/i] [/b]
主要这个问题比较特殊,棋盘是矩形。如果棋盘是正多边形(比如八边形)之类,模剩余类就要分成非常很多种情况,组合起来的情况就复杂多了。从编程数值计算的角度考虑,当然是用取整表达形式更方便。

业余的业余 发表于 2019-4-20 04:43

[b]回复 [url=http://kuing.orzweb.net/redirect.php?goto=findpost&pid=30904&ptid=6019]23#[/url] [i]kuing[/i] [/b]

换了个算法,不存储棋盘状态,这回N(10,11)通过(手提耗CPU时间16分+),答案与你的相同。{:lol:}

这个算法应该可以很容易调整到两种色块(我把题目变成 $n\times n$ 的棋盘,其中特定个数的格子按照要求的规则涂成指定的颜色), 比如 $l$ 个红色块, $m$ 个蓝色块 ($l,m <n$), 去掉旋转和镜像对称后的情形。如果准备试两种颜色的情形,可以提供快捷的验证服务。

页: [1]

Powered by Discuz! Archiver 7.2  © 2001-2009 Comsenz Inc.