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

青青子衿

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

en.wikipedia.org/wiki/Rook_polynomial

realnumber

旋转翻转等价的话，
一个車的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)累加即可.

-----没注意到不同行，不同列 ，错误留着吧.

Infinity

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

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

棋盘中两条对称轴可将棋盘划分为四个等大的小棋盘，由于考虑旋转和翻转，因此两个車的分布情况无非就三种情况：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$种。

青青子衿

综上，nxn棋盘考虑旋转和翻转，当n为奇数时，两車的落子方案有$(n-1)^2(2n^2+7n+9)/16$种；当n为偶数时，两車的落子方案有$n^2(2n^2-5n+6)/16$种。
Infinity 发表于 2019-4-14 21:38

可是，为什么我算出来的是这个呢？
\[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}\]
...

1. DiscretePlot[
2. Piecewise[{{(n (n^3 - 2 n^2 + 6 n - 4))/16, Mod[n, 2] == 0},
3.    {((n - 1) (n^3 - n^2 + 5 n - 1))/16, Mod[n, 2] == 1}}],{n, 20}]

复制代码

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

回复 4# 青青子衿
我也不保证自己计算是否有遗漏。你可以把你的计算过程写下来，不然没法判断问题在哪呀。

kuing

声明一下，我理解的翻转是沿着与棋盘网格平行的两条对称轴进行的。当然也可使用对角线作为对称轴翻转，不过结果（数量）是否一样，未作分析。 ...
Infinity 发表于 2019-4-14 21:38

你理解的翻转与旋转的复合就可以得出对角线翻转。
比如：逆时针旋转 90 度 * 左右翻转 = 沿 y=x 翻转；顺时针旋转 90 度 * 左右翻转 = 沿 y=n-x 翻转。
所以旋转及左右翻转等价实际上已经包含了对角线翻转等价。

Infinity

回复 6# kuing
对哦，也可以这样复合，那么就是等价的了。这样说来，上面给出的结果就不对了，因为我没有考虑对角线对称的问题。

kuing

照抄前些天的这帖 kuing.cjhb.site/forum.php?mod=redirect&goto=findpost&ptid=5979&pid=30608 好了

记 `\{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、为啥你的代码到处都是 \,

\(\,n\times\,n\,\)

…………

青青子衿

照抄前些天的这帖 ...
kuing 发表于 2019-4-16 18:45

KK是真的强

结果和纸巾的一样。
PS、为啥你的代码到处都是 \,

\(\,n\times\,n\,\)

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

是这样的……LaTeX代码中，打一些以字母结尾的命令时，总是会因为与后面的字母黏在一起而报错所以就养成了一个奇怪的习惯（加逗号）

Infinity

回复 8# kuing
如果变成三个或是更多的情况怎么分析？感觉Burnside引理在棋子数（或者染色数）比较少的情况下还可以用，对于比较大的情形一般用Polya定理，但对于它对于约束的解决比较麻烦。

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

kuing

回复 10# Infinity

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

同类的三只車：
\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 种：

如果还有的话，那就是我错了……其他情况实在不好枚举……

青青子衿

回复 11# kuing
kk，睡得真晚~

是否正确，其实我也没什么把握，要是有程序验证一下就好了，可是不知怎么编，谁有办法？
kuing 发表于 2019-4-17 01:27

4*4的棋盘放四个既不同行也不同列的車，之前玩过
参见：bbs.emath.ac.cn/thread-5375-1-1.html

（发现Oeis上收录的序列是：n×n的棋盘放n个既不同行也不同列的車；
目前为止，并没有收录：n×n的棋盘放2个既不同行也不同列的車）

考虑每行每列有且仅有一个\(\,1\,\)的\(\,4\times4\,\)二进制方阵；
若考虑旋转等价（oeis.org/A263685），那么这样的二进制方阵有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*}
,,,

1. e = Identity;
2. f = Reverse;
3. g = Transpose;
4. Grot = {e, f@*g, g@*f, f@*g@*f@*g};
5. MatrixPlot[#, ImageSize -> Tiny, ColorFunction -> "Monochrome"] & /@
6. DeleteDuplicates[
7.   SparseArray@Thread[Transpose[{Range[4], #}] -> 1] & /@
8.    Permutations@Range[4], MemberQ[Through@Grot[#1], #2] &]

复制代码

...

若考虑旋转翻转等价（oeis.org/A000903），那么这样的二进制方阵有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*}
,,,

1. e = Identity;
2. f = Reverse;
3. g = Transpose;
4. Grotflip = {e, f, g, f@*g, g@*f, f@*g@*f, g@*f@*g, f@*g@*f@*g};
5. MatrixPlot[#, ImageSize -> Tiny, ColorFunction -> "Monochrome"] & /@
6. DeleteDuplicates[
7.   SparseArray@Thread[Transpose[{Range[4], #}] -> 1] & /@
8.    Permutations@Range[4], MemberQ[Through@Grotflip[#1], #2] &]

复制代码

...

kuing

回复 12# 青青子衿

程序看不懂
有没有 4*4 放三个或 5*5 放四个的？

Infinity

回复 11# kuing
仿照12楼可编写如下程序验证nxn棋盘，k个車的分布种数

1. e = Identity; f = Reverse; g = Transpose;
2. Grot = {e, f@*g, g@*f, f@*g@*f@*g};
3. Grotflip = {e, f, g, f@*g, g@*f, f@*g@*f, g@*f@*g, f@*g@*f@*g};
4. n = 4; k = 3;
5. s = SparseArray[#, {n,
6.       n}] & /@ (Table[# ->
7.          1 & /@ (Transpose@{Subsets[Range[n], {k}][[i]],
8.           Permutations[Range[n], {k}][[j]]}), {i, 1,
9.        Binomial[n, k]}, {j, 1, FactorialPower[n, k]}] //
10.      Flatten[#, 1] &);
11. MatrixPlot[#, ColorRules -> {1 -> RGBColor[1, .75, .5]},
12.    ImageSize -> Tiny, Mesh -> All, Frame -> None,
13.    FrameTicks -> None] & /@
14. DeleteDuplicates[s, MemberQ[Through@Grotflip[#1], #2] &]
15. % // Length

复制代码

4x4棋盘2車分布

kuing

回复 14# Infinity

多谢！very nice!

青青子衿

回复 14# Infinity
那个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*}

1. Table[Piecewise[{
2.    {(n (n^3 - 2 n^2 + 6 n - 4))/16, Mod[n, 2] == 0},
3.    {((n - 1) (n^3 - n^2 + 5 n - 1))/16, Mod[n, 2] == 1}
4.    }], {n, 20}]
5. Table[Piecewise[{
6.    {(n (n - 1) (n - 2) (n^3 - 3 n^2 + 2 n + 8))/48, Mod[n, 2] == 0},
7.    {((n^2 - 1) (n^4 - 6 n^3 + 14 n^2 - 10 n - 3))/48, Mod[n, 2] == 1}
8.    }], {n, 20}]
9. Table[Piecewise[{
10.    {(n (n - 2) (n^6 - 10 n^5 + 38 n^4 - 68 n^3 + 80 n^2 - 104 n + 72))/192,
11.           Mod[n, 2] == 0},
12.    {((n - 1) (n - 3) (n^6 - 8 n^5 + 23 n^4 - 28 n^3 + 35 n^2 - 52 n + 21))/192,
13.          Mod[n, 2] == 1}
14.    }], {n, 20}]

复制代码

...
\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*}
,,,

1. Table[Piecewise[{
2.    {(n (n - 1) (n - 2) (n - 3) (n - 4)
3.          (n^5 - 10 n^4 + 35 n^3 - 50 n^2 + 24 n + 52))/960,
4.          Mod[n, 2] == 0},
5.    {((n - 1) (n - 3)
6.         (n^8 - 16 n^7 + 103 n^6 - 340 n^5 + 604 n^4
7.          - 492 n^3 - 105 n^2 + 356 n + 105))/960,
8.         Mod[n, 2] == 1}
9.    }], {n, 20}]

复制代码

kuing

同类的五只車，比四只还简单些：
\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 为 {2, 16, 86, 320, 956, 2408, 5380, 10920}
`N_4` 取 `n` 由 4~10 为 {7, 89, 723, 3773, 14914, 47982, 132930}
`N_5` 取 `n` 由 5~10 为 {23, 579, 6762, 47404, 238998, 954198}
其中红色的数字已通过 14# 的程序验证，其中 `N_4` 的 3773 跑了差不多两小时所以也不敢去跑下面的 6762 了……

Infinity

回复 17# kuing
当n增大时，矩阵变得很大，相应不考虑旋转和翻转的布子结果增加很多，从而需要删除重复的比对过程非常慢。
由于结果是多项式，因为高次多项式振荡趋势比较强，所以对结果很敏感，只要有一两个对就说明不会错。相应地，低次多项式则需要多验证才行，因为变化平滑，容易出现部分结果符合而后面不符合。
相信你的计算没问题。我们可以验证中间结果（比如f1,f2,f3,f7)来减少计算量。
比如下面代码可验证顺时针180旋转的不动点个数（17楼中的f3）

1. n = 7; k = 5;
2. s = SparseArray[#, {n,
3.      n}] & /@ (Table[# ->
4.         1 & /@ (Transpose@{Subsets[Range[n], {k}][[i]],
5.          Permutations[Range[n], {k}][[j]]}), {i, 1,
6.       Binomial[n, k]}, {j, 1, FactorialPower[n, k]}] //
7.     Flatten[#, 1] &);
8. Select[s, SameQ[f@*g@*f@*g@#, #] &]//Length

复制代码

kuing

回复 18# Infinity

谢谢！
这个程序我大概能看懂，验证其他的就改最后一行
{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}

业余的业余

同类的五只車，比四只还简单些：
\begin{align*}
f_1\colon &&& \frac{n^2(n-1)^2(n-2)^2(n-3)^2(n-4)^2}{5 ...
kuing 发表于 2019-4-17 18:18

$N_5$ 后面的数字都验证无误。 接下来的 $11_5=3204768$.