n个大小相同的圆珠，其中k个红色，n-k个绿色

realnumber

1.n个大小相同的圆珠，其中k个红色，n-k个绿色，穿成一个手环，（旋转或按手环所在平面翻转能够颜色能重合的认为是同一种，例如"rgrrgrrrg"与"rgrrrgrrg"翻转后能重合，认为是同一种），记不同的排列种数为f(n,k),试求相关的问题，表达式，递推性质，...
或者求几个特殊的。

2.n个大小相同的圆珠，其中k个红色，n-k个绿色，镶在圆盘上，（旋转后能重合的认为是同一种，例如"rgrrgrrrg"与"rrgrrrgrg"认为是同一种），记不同的排列种数为g(n,k),试求相关的问题，表达式，递推性质，...或者求几个特殊的。



我也不晓得有没有简单结果，在考虑别的问题时联想到的.

kuing

可能要用上Pólya定理什么的，一般情况应该很复杂。

比较简单的情形，就是当 $k$ 与 $n$ 互素时，此时每种排列的自身不会有对称性，故在 $C_n^k$ 中每种排列被重复计算 $n$ 次，所以此时结果为 $C_n^k/n$。不互素就比较复杂了，晚点再想……

abababa

回复 2# kuing

就是用波利亚定理，以前看过一个立体的题，网友给讲过，不过我用不好，人教论坛也有相关的帖子。
如果形状不同，结果也不一样，比如6个物品，可以排成正三角形顶点加各边中点，也可以排成正六边形只算顶点，这样结果可能就不相同了，因为对称轴不一样。

hbghlyj

项链多项式(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$$

hbghlyj

这份计算机科学讲义的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.

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.


Table 9.2.1 Inventory for 5 -beaded necklaces under cyclic symmetry.

Figure 9.2.5 illustrates the eight necklaces.

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.

hbghlyj

为啥5#的代码画不出来?

1. \usetikzlibrary{shapes.geometric}
2. \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}}]
3. \def\ngon{5}
4. \node[draw, regular polygon,regular polygon sides=\ngon,minimum size=3cm] (p) {};
5. \foreach\x in {1,...,\ngon}{
6.     \node[mystyle=\x] (p\x) at (p.corner \x){};
7. }
8. \end{tikzpicture}

Copy the Code

我在upmath.me官网上画却是可以画出来.

爪机专用

回复 6# hbghlyj

似乎是因为有#号的原因（#在链接里有别的意思？）

在upmath上#生成的链接是变成%23
晚点我修改一下代码
=====
已解决，5#图已正常显示
原先以为改用 encodeURIComponent 就行，又发现会把 < 里的 & 啥的也转了，还是加个 replace(/#/g,'%23') 好了。

Czhang271828

以前写的的文章，晚点想想推广（例如群在二元集合上的作用等等）

isee

回复 8# Czhang271828

学（看）习（看）学（看）习（看）

Czhang271828

回复 8# Czhang271828



简单来说, 该类计数问题通解如下:

Step 1: 将问题转化为群作用问题. 就项链计数而言, 记 $\Omega$ 为所有对象 (不考虑旋转翻转下等价, 例如两黑珠一白珠可组成 $3$ 条项链).

Step 2: 考虑旋转翻转作用, 即二面体群 $D_{n}$ 在 $\Omega$ 上的作用. $x\in \Omega$ 在旋转翻转下能生成的所有对象为轨道 $Gx:=\{gx:g\in\Omega\}$. 两黑珠一白珠的项链在正三角形变换群下可生成三个不同的对象, 即生成大小为 $3$ 的轨道.

Step 3: 记 $\Gamma:=\{(g,x):gx=x\}$​ 为不动点数量. Burnside 引理给出
$$
\sum_{g\in G}|\{x:gx=x\}|=|\Gamma|=|G|\cdot\text{所有轨道数量}.
$$
待求值即"考虑旋转翻转变换下等价的项链种数", 亦即轨道数量.

Step 4: 因此轨道数为
$$
\dfrac{1}{|G|}\sum_{g\in G}|\{x:gx=x\}|.
$$
该类计数方法的难点就是计算群中所有元素的不动点数量.

其他例子不举了, 这篇资料写得已经很好了.