這道組合數學問題怎麽做？

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 .