免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 两色染九宫格(旋转翻转等价)

\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*}
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

找到了!“二进制n阶矩阵”
二进制三阶矩阵在旋转、翻转等价下有102种!
http://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}\]

TOP

看看这个公式是怎么的出来的
\[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}\]

TOP

无标题.png
2019-3-25 18:25

TOP

无标题.png
2019-3-25 19:05


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

TOP

加起来不是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*}

TOP

复习了一下 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# 的一样了。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

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

现在改为用 `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……
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

返回列表 回复 发帖