[问题] 用黑白两种颜色给正 n 边形的边染色( n\geq 3 ) , 有几种本质不同的方法?
[答案]
这个问题是 项链计数问题.
[项链计数问题] 用 r 种不同颜色的珠子能串成多少种 n 颗珠子的项链?
这个问题可以描述为: 有正 n 边形, 它的顶点集合是 \left\{ 1,2,...,n \right\} , 用颜色集 C=\left\{ c_1,c_2,...,c_r \right\} 染色. 设 X 是这 r 种颜色组成的 n 元组的集合, 若 x\in X , 则 x=(x_1,x_2,\cdots,x_n) . 二面体群 \mathsf D_n=\langle \sigma,\tau |\sigma^n=\tau^2=1 ,\ \tau\sigma\tau=\sigma^{-1}\rangle 作用在 X 上, |\mathsf D_n|=2n , 轨道的条数 N 就是染色的种类.
[例子] 正三角形用黑白两种颜色染色, 请问有几种染色方法?
[答案] D_2(3)=\frac{1}{6} \sum_{d \, | \, 3}\varphi(\frac{3}{d}) 2^{d} + \frac{1}{2}2^{2}=4 .[例子] 正方形用黑白两种颜色染色, 请问有几种染色方法?
[答案] D_2(4)=\frac{1}{8} \sum_{d \, | \, 4}\varphi(\frac{4}{d}) 2^{d}+ \frac{1}{4}2^{2}\cdot 3=6 .