棋盘着色方案设计.docVIP

棋盘着色方案设计 设有一个N*N的棋盘，要用M种颜色对其着色，棋盘的每个方格可以用M种颜色的任一种。考虑旋转等价性，问共可得到多少不同的棋盘。 问题分析：每个方格有M种着色方法，故共有M的N*N次方种着色方法。设其构成的集合为 S。 考虑棋盘的旋转。分别用置换π1，π2，π3代表棋盘绕中心顺时针旋转90度、180度、270度。用π0表示单位置换。则{π0，π1，π2，π3}构成置换群，设为G。G诱导的等价关系把S分成若干个等价类。S中两个元素对应同一个棋盘当且仅当它们属于同一个等价类。不同的棋盘数应等于等价类的数目。 根据burnside定理：由S的置换群诱导的等价关系将S划分所得的等价类数目等于 ∑ψ（σ）/|G|，（σ∈G）。其中ψ（σ）表示在置换σ下保持不变的元素个数。 如何计算置换σ下保持不变的元素个数呢？对于每一次旋转，若存在某种着色，使得它的每个方格与它旋转到的方格颜色都相同，则可以认为该着色对于该旋转是保持不变的。因为一次旋转对应一个置换，而每一个置换都可以分解成循环置换的乘积。若每个循环置换的所有元素对应的方格颜色相同，则该着色对于该旋转是保持不变的。因此要寻找某个置换下保持不变的元素个数，只须把该置换分解成循环置换的乘积，让每个循环置换的所有元素着色相同。故共分解成几个循环置换的乘积，就有M的几次方种着色在该置换下保持不变。 以M=2，N=4为例。 10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4 图（1） 7 8 9 10 6 15 16 11 5 14 13 12 4 3 2 1 图（2） 置换π1相当于由图（1）到图（2）所做的旋转。即 （1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ） 4 5 6 7 8 9 10 11 12 1 2 3 14 15 16 13 =（1 4 7 10）（2 5 8 11）（3 6 9 12）（13 14 15 16） 共分解成4个循环置换的乘积，棋盘在π1下保持不变当且仅当方格1，4，7，10颜色相同，2，5，8，11颜色相同，3，6，9 ，12颜色相同，13，14，15，16颜色相同。 故ψ（π1）=2^4 同理，由π2=π1^2,π3=π1^3 ψ（π2）=2^8,ψ（π3）=2^4. 显然，ψ（π0）=2^16。故不同的棋盘数等于 1/4（2^16＋2^4＋2^8＋2^4）=16456