本帖最后由 hbghlyj 于 2022-2-21 08:26 编辑 项链多项式(Necklace polynomial)
$M(α,n)$ counts the number of distinct necklaces of $n$ colored beads chosen out of $α$ available colors.
$$\alpha^n \ =\ \sum_{d\,|\,n} d \, M(\alpha, d)$$$$M(\alpha,n) \ =\ {1\over n}\sum_{d\,|\,n}\mu\!\left({n \over d}\right)\alpha^d$$
这份计算机科学讲义的37页: Coloring Necklaces
We conclude this section with an application to a classic example, that of counting necklaces. Our model for an $n$-beaded necklace is a geometric conceptualization of the cycle graph $C_{n}$ as a regular $n$-sided polygon, as illustrated in Figure 9.2.4. The numbering of the beads is used in specification of the permutations.
[tikz]\usetikzlibrary{shapes.geometric}
\begin{tikzpicture}[mystyle/.style={draw,shape=circle,fill=white, inner sep=0pt, minimum size=4pt, label={[anchor=center, label distance=2mm](90+360/\ngon*(#1-1)):#1}}]
\def\ngon{5}
\node[draw, regular polygon,regular polygon sides=\ngon,minimum size=3cm] (p) {};
\foreach\x in {1,...,\ngon}{
\node[mystyle=\x] (p\x) at (p.corner \x){};
}
\end{tikzpicture}[/tikz]
Example 9.2.7: Suppose that each bead is to be colored either black or white, and that two necklaces are indistinguishable (i.e., equivalent) if one can be obtained from the other by a rotation of the polygon. We model these symmetries by the cyclic permutation group $\mathbb{Z}_{5}$, in which the clockwise rotation of $\frac{2 \pi}{5}$ corresponds to the permutation
$$
\alpha=\left(\begin{array}{lllll}
1 & 2 & 3 & 4 & 5
\end{array}\right)
$$
The cycle structure of the identity permutation is $t_{1}^{5}$. By Corollary 9.1.2, the cycle structure of the permutations
$$
\alpha, \quad \alpha^{2}, \quad \alpha^{3}, \quad \text { and } \quad \alpha^{4}
$$
is $t_{5}$. Thus, the cycle index polynomial is
$$
\mathcal{Z}_{\mathbb{Z}_{5}}=\frac{1}{5}\left(t_{1}^{5}+4 t_{5}\right)
$$
According to Theorem 9.2.8, the number of 2-colored, 5-beaded necklaces is$$
\frac{1}{5}\left(2^{5}+4 \cdot 2\right)=\frac{40}{5}=8
$$
Table 9.2.1 provides the corresponding Pólya inventory.
Fig 9.2.5 The eight 2-colored, 5-beaded necklaces.
Allowing reflections cannot increase the number of equivalence classes, since any two necklaces that are related by a rotation remain related by that rotation when reflections are included.
新浪微博
QQ空间
人人网
腾讯微博
Facebook
Google+
Plurk
Twitter
Line
发表于 2017-7-10 09:10
| 
QQ空间
腾讯微博
腾讯朋友
发表于 2017-7-10 13:57
| 
