这道组合数学问题怎么做？

2021-06-16知识

[问题] 用黑白两种颜色给正 n 边形的边染色( n\geq 3 ) , 有几种本质不同的方法?

[答案]

当 n 为奇数时, 不等价的染色数目为 D_2(n)=\frac{1}{2n} \sum_{d \, | \, n}\varphi(\frac{n}{d}) 2^{d} + \frac{1}{2}2^{\frac{n+1}{2}} ；

当 n 为偶数时, 不等价的染色数目为 D_2(n)=\frac{1}{2n} \sum_{d \, | \, n}\varphi(\frac{n}{d}) 2^{d}+ 3\cdot 2^{\frac{n}{2}-2} .

这个问题是 项链计数问题.

[项链计数问题] 用 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 就是染色的种类.

当 n 为奇数时, 不等价的项链数目为 D_r(n)=\frac{1}{2n} \sum_{d \, | \, n}\varphi(\frac{n}{d}) r^{d} + \frac{1}{2}r^{\frac{n+1}{2}} ；

当 n 为偶数时, 不等价的项链数目为 D_r(n)=\frac{1}{2n} \sum_{d \, | \, n}\varphi(\frac{n}{d}) r^{d}+ \frac{1}{4}r^{\frac{n}{2}}(1+r) .

[例子] 正三角形用黑白两种颜色染色, 请问有几种染色方法?

[答案] 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 .