两色染九宫格（旋转翻转等价）

青青子衿

\begin{align*}  
&p=1&&\blacksquare&&\square\\  
&p=4&&\overset{\Large{\blacksquare}}{\blacksquare}\overset{\Large{\blacksquare}}{\blacksquare}&&\overset{\Large{\square}}{\square}\overset{\Large{\square}}{\square}\\
&&&\overset{\Large{\square}}{\blacksquare}\overset{\Large{\blacksquare}}{\blacksquare}&&\overset{\Large{\blacksquare}}{\square}\overset{\Large{\square}}{\square}\\
&&&\overset{\Large{\square}}{\blacksquare}\overset{\Large{\square}}{\blacksquare}\\
&&&\overset{\Large{\square}}{\blacksquare}\overset{\Large{\blacksquare}}{\square}\\
&p=9&&\overset{\Large\overset{\huge{\square}}{\blacksquare}}{\blacksquare}\overset{\Large\overset{\huge{\blacksquare}}{\blacksquare}}{\blacksquare}\overset{\Large\overset{\huge{\blacksquare}}{\blacksquare}}{\blacksquare}&&\overset{\Large\overset{\huge{\blacksquare}}{\square}}{\square}\overset{\Large\overset{\huge{\square}}{\square}}{\square}\overset{\Large\overset{\huge{\square}}{\square}}{\square}\\
&&&\overset{\Large\overset{\huge{\square}}{\blacksquare}}{\blacksquare}\overset{\Large\overset{\huge{\square}}{\blacksquare}}{\blacksquare}\overset{\Large\overset{\huge{\blacksquare}}{\blacksquare}}{\blacksquare}&&\overset{\Large\overset{\huge{\blacksquare}}{\square}}{\square}\overset{\Large\overset{\huge{\blacksquare}}{\square}}{\square}\overset{\Large\overset{\huge{\square}}{\square}}{\square}\\
&&&\quad\vdots
\end{align*}

青青子衿

找到了！“二进制n阶矩阵”
二进制三阶矩阵在旋转、翻转等价下有102种！
oeis.org/A054247

\begin{align*}
a(3)&=\,\dfrac{1}{8}\left(2^{3^2}+2\cdot2^{(3^2+3)/4}+2^{(3^2+1)/2}+4\cdot2^{(3^2+3)/2}\right)\\
&=\,\dfrac{1}{8}\left(2^{9}+2\cdot2^3+2^5+4\cdot2^6\right)=\dfrac{2^9+2^4+2^5+2^8}{8}=\,\quad{\large\color{red}{102}}
\end{align*}

\[a(n) =\begin{cases}\dfrac{1}{8}\left(2^{n^2}+2\cdot2^{n^2/4}+3\cdot2^{n^2/2}+2\cdot2^{(n^2+n)/2}\right) & n= 0\pmod2 \\
\dfrac{1}{8}\left(2^{n^2}+2\cdot2^{(n^2+3)/4}+2^{(n^2+1)/2}+4\cdot2^{(n^2+n)/2}\right)& n= 1\pmod2\end{cases}\]

Infinity

看看这个公式是怎么的出来的
\[a(n) =\begin{cases}\displaystyle \frac 18(2^{n^2}+2*2^{n^2/4}+3*2^{n^2/2}+2*2^{(n^2+n)/2}) & n= 0\pmod2 \\\displaystyle\frac18(2^{n^2}+2*2^{(n^2+3)/4}+2^{(n^2+1)/2}+4*2^{(n^2+n)/2})& n= 1\pmod2\end{cases}\]

游客

游客

加起来不是51.。。。不知道哪出错了

青青子衿

加起来不是51.。。。不知道哪出错了
游客 发表于 2019-3-25 19:06

四个白色五个黑色的情形中，你漏了下面这种情形：
\begin{align*}
\overset{\Large\overset{\huge{\blacksquare}}{\square}}{\blacksquare}\overset{\Large\overset{\huge{\square}}{\blacksquare}}{\square}\overset{\Large\overset{\huge{\blacksquare}}{\square}}{\blacksquare}
\end{align*}
还有全白的情形
\begin{align*}
\overset{\Large\overset{\huge{\square}}{\square}}{\square}\overset{\Large\overset{\huge{\square}}{\square}}{\square}\overset{\Large\overset{\huge{\square}}{\square}}{\square}\\
\end{align*}

kuing

复习了一下 Burnside 引理，玩得太少，几乎忘了。

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

先计算 `n` 为偶数时，`f_1` 的自然是全部，即 `2^{n^2}`；

对于 `f_2`，要使旋转90度后不变，只要 1/4 的格子被取定（比如第一象限内的），其余就定了，所以是 `2^{n^2/4}`，对 `f_4` 同理；

同样道理，对于 `f_3`，即旋转180度后不变，就是取定一半，即 `2^{n^2/2}`，对 `f_5` 及 `f_6` 也同理；

对于 `f_7`，对称轴上的任取，然后取定剩下的一半，所以是 `2^n\cdot2^{(n^2-n)/2}`，对 `f_8` 同理。

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

再计算 `n` 为奇数时，`f_1` 的全部 `2^{n^2}`；

`f_2` 的，正中心任取，然后取定剩下的 1/4，所以是 `2\cdot2^{(n^2-1)/4}`，对 `f_4` 同理；

`f_3` 的，正中心任取，然后取定剩下的一半，所以是 `2\cdot2^{(n^2-1)/2}`；

`f_5` 的，对称轴上的任取，然后取定剩下的一半，所以是 `2^n\cdot2^{(n^2-n)/2}`，对 `f_6`, `f_7`, `f_8` 均同理。

综上，由 Burnside 引理得结果就是
\[\frac{2^{n^2}+2\cdot2\cdot2^{(n^2-1)/4}+2\cdot2^{(n^2-1)/2}+4\cdot2^n\cdot2^{(n^2-n)/2}}8.\]

化简后就和 2# 的一样了。

kuing

继续复习，进一步当然就是波利亚定理了，其表明只需看置换的循环个数即可（其实楼上写到后面就感觉到是这样）。

现在改为用 `m` 种颜色来染，继续沿用上面的那些 `f`，用波利亚定理来表述的话，大概就是这样：

还是先看偶数，`f_1` 全是 1 循环，共 `n^2` 个；

`f_2`, `f_4` 都全是 4 循环，共 `n^2/4` 个；

`f_3`, `f_5`, `f_6` 都全是 2 循环，共 `n^2/2` 个；

`f_7`, `f_8` 则是对称轴上 1 循环，其余 2 循环，共 `n+(n^2-n)/2=(n^2+n)/2` 个循环。

所以结果就是
\[\frac{m^{n^2}+2\cdot m^{n^2/4}+3\cdot m^{n^2/2}+2\cdot m^{(n^2+n)/2}}8;\]

奇数的，`f_1` 全是 1 循环，共 `n^2` 个；

`f_2`, `f_4` 都是中心 1 循环，其余 4 循环，共 `1+(n^2-1)/4=(n^2+3)/4` 个循环；

`f_3` 是中心 1 循环，其余 2 循环，共 `1+(n^2-1)/2=(n^2+1)/2` 个循环；

`f_5`, `f_6`, `f_7`, `f_8` 都是对称轴上 1 循环，其余 2 循环，共 `n+(n^2-n)/2=(n^2+n)/2` 个循环。

所以结果就是
\[\frac{m^{n^2}+2\cdot m^{(n^2+3)/4}+m^{(n^2+1)/2}+4\cdot m^{(n^2+n)/2}}8.\]

呐，其实就是将 2# 的公式中的底数 2 都变成了 m……