例題
給3x3的格子上色，4種顏色，可以重復，排除旋轉后相同的情況，請問有多少種不同的上色方法？
解答
設格子編號如下：
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
每種旋轉是為一種置換，定義為\(g_i\)，共4種置換：
\[g_1 = <旋轉0° > \\ g_2 = <旋轉90° > \\ g_3 = <旋轉180° > \\ g_4 = <旋轉270° > \]\(D(g_i)\)表示在\(g_i\)這種置換的作用下沒有改變狀態的方案集合，\(|D(g_i)|\)表示其元素個數，以下分情況討論：
- 旋轉\(0°\)
旋轉0°怎么都不會變, 計算隨便涂的總數即可：
-
旋轉\(90°\)
{1、3、7、9}回圈變換，{2、4、6、8}回圈變換， {5}永遠不變，置換群為(1379)(2468)(5)，(1379)可取4種顏色，(2468)可以取4種顏色， (5)可以取4種顏色，總方案數：
-
旋轉\(180°\)
置換群為(19)(28)(37)(46)(5)，總方案數：
-
旋轉\(270°\)
類似旋轉90°，總方案數：
根據Burnside引理，設\(G\)為所有置換的集合，總方案數：
\[L=\frac{1}{|G|} \sum_{\mathrm{i}=1}^{|G|}\left|D\left(g_{i}\right)\right| = \frac{1}{4}(4^9+4^3+4^5+4^3)=65824 \]或直接用Polya定理，設\(m\)種顏色給\(n\)個物件染色，\(C_i\)為每種置換下的回圈節,則有：
\[L=\frac{1}{|G|}\left[m^{C_{1}}+m^{C_{2}}+\cdots+m^{C_{g-1}}+m^{C_{g}}\right] = \frac{1}{4}(4^9+4^3+4^5+4^3)=65824 \] 數學是符號的藝術，音樂是上界的語言，轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/465993.html
標籤：其他
上一篇：Vulnhub-DC-4靶機實戰