组合计数在图形中的问题

yoyo987654

$4 \times 4$ 的棋盘中有 16 个小正方格，将其中 4 个方格涂成黑色，有多少种不同的方法？
（在平面旋转后可以重合的，视为同一种方法）
这题涉及旋转重合的问题，不太肯定，求指教

kuing

以前撸过类似题：
forum.php?mod=viewthread&tid=5979
forum.php?mod=viewthread&tid=6019

又隔了好长时间，Burnside 引理又快忘了，又得复习一下。

记 `\{f_1,f_2,f_3,f_4\}` 表示 `\{`不动，旋转90度，旋转180度，旋转270度`\}`，计算各 `f_i` 作用下不变的染色数。

`f_1` 即全部：`C_{16}^4`；

对于 `f_2`，将棋盘横竖分成四块，每块染一格且旋转90度相同，显然只有 4 种，对 `f_4` 同理；

对于 `f_3`，要旋转180度后不变，只需取定一半，所以是 `C_8^2`。

综上，由 Burnside 引理得结果就是
\[\frac{C_{16}^4+4+C_8^2+4}4=464.\]

yoyo987654

\begin{aligned}
\text{答案} & =4+\frac{16-4}{2}+\frac{1820-16}{4} \\
& =4+6+451 \\
& =461
\end{aligned}
想问问这个答案是否有误

tommywong

yoyo987654 发表于 2023-8-27 10:35
想问问这个答案是否有误

設:
$U$為所有方法
$A$為旋轉90度後重合嘅方法
$B$為旋轉180度後重合嘅方法
$C$為旋轉270度後重合嘅方法

$A=C\subset B\subset U$

$\displaystyle |A|=4, |B|=\binom{8}{2}=28,~|U|=\binom{16}{4}=1820$

每個$U-B$嘅方法都有4種互相重合
每個$B-A$嘅方法都有2種互相重合
$4+\dfrac{28-4}{2}+\dfrac{1820-28}{4}=464$

#3答案誤處：
$4+\dfrac{28-4}{2}=4+12=16$
#3答案誤將排除重複後的數目從未排除重複的所有方法中抽走
並對已排除重複後的數目再除以二