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

色k

回复 20# 业余的业余

你用什么方法验证的呀？

业余的业余

回复 21# 色k

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

kuing

回复 22# 业余的业余

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

`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}

如果都正确，那我刚才推出的一般公式看来就没问题了

业余的业余

回复 23# kuing

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

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

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

kuing

回复 24# 业余的业余

谢谢，那我就放心发了

同类 `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

根据此公式用 MMC(A) 列出那些数字：

1. 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]}]
2. BB[m_, n_] := 2 Binomial[Floor[n/2], Floor[m/2]] Binomial[Floor[m/2], Floor[m/4]] Floor[m/4]!
3. CC[m_, n_] := Binomial[Floor[n/2], Floor[m/2]]^2*2^(Floor[m/2]) Floor[m/2]!
4. NN[m_, n_] := If[EvenQ[n] && OddQ[m], AA[m, n]/8,
5. If[EvenQ[n] && (Mod[m, 4] == 2) || OddQ[n] && (Mod[m, 4] >= 2), (AA[m, n] + CC[m, n])/8,
6. If[EvenQ[n] && (Mod[m, 4] == 0) || OddQ[n] && (Mod[m, 4] < 2), (AA[m, n] + BB[m, n] + CC[m, n])/8]]]
7. Table[NN[i, j], {i, 2, 11}, {j, i, i + 5}] // MatrixForm

复制代码

输出：
\[\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

回复 19# kuing
是的。上面的代码也是全局排除法找到某个置换下的不变布子方案。

其实按照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

回复 27# Infinity

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

kuing

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

Infinity

回复 28# kuing
我这几天有事没注意帖子更新了回复，今天直接回复后才发现你已经弄了。本来我也想直接用取整函数的，能统一表达，只是那样的解析性质不太好（不利于分析），所以又改回来了。

程序我待会儿发出来。

青青子衿

楼上的答复都太精彩了
\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

回复 30# Infinity

嗯，说得有道理，好看未必好用

另一种写法：
\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

其实MMA是函数式编程，如果采用这种风格，将会"智能地"按照函数定义规则去执行，这一过程非常符合人类的数学逻辑过程，编写起来也非常流畅。
由于只计算数字结果，所以可以将27楼结果相应用取整函数替代各种模剩余类后，按照函数式编程如下：

1. f1[n_, m_] := m! Binomial[n, m]^2;
2. f24[n_?OddQ, m_ /; Mod[m, 4] >= 2] = 0;
3. f24[n_?EvenQ, m_ /; Mod[m, 4] > 0] = 0;
4. f24[n_, m_] := FactorialPower[Floor[n/2], Floor[m/2]]/Floor[m/4]!
5. f3[n_?EvenQ, m_?OddQ] = 0;
6. f3[n_, m_] :=
7.   2^Floor[m/2] FactorialPower[Floor[n/2], Floor[m/2]]^2/Floor[m/2]!;
8. f78[n_, m_] :=
9.   Sum[FactorialPower[n, 2 k] Binomial[n - 2 k, m - 2 k]/(2^k k!), {k,
10.     0, Floor[m/2]}];
11. Chess[n_Integer?Positive,
12.    m_Integer?
13.     Positive] := (f1[n, m] + 2 f24[n, m] + f3[n, m] + 2 f78[n, m])/8;
14. Table[Chess[n, m], {m, 2, 11}, {n, m, m + 5}]

复制代码

返回结果跟26楼一样。
当然，像31楼那样的上对角矩阵使得行列意义更加明显：

1. Table[If[i <= j, Chess[j, i], 0], {i, 2, 11}, {j, 2, 11}]

复制代码

Infinity

回复 32# kuing
主要这个问题比较特殊，棋盘是矩形。如果棋盘是正多边形(比如八边形）之类，模剩余类就要分成非常很多种情况，组合起来的情况就复杂多了。从编程数值计算的角度考虑，当然是用取整表达形式更方便。

业余的业余

回复 23# kuing

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

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