主题
Search

项链


Necklace

在技术组合意义上,长度为 na 元项链是由 n 个字符组成的字符串,每个字符有 a 种可能的类型。旋转被忽略,即 b_1b_2...b_n 等价于对于任何 kb_kb_(k+1)...b_nb_1b_2...b_(k-1)

固定项链中,字符串的反转被认为是不同的,因此它们表示珠子的环形集合,其中项链不能从平面中拿起(即,相反的朝向不被认为是等价的)。由 a 种类型的珠子组成的长度为 n 的固定项链的数量 N(n,a) 由下式给出

 N(n,a)=1/nsum_(i=1)^(nu(n))phi(d_i)a^(n/d_i),
(1)

其中 d_in约数,其中 d_1=1, d_2, ..., d_nu(n)=n, nu(n)n约数的数目,phi(x)欧拉函数

对于自由项链,相反的朝向(镜像)被认为是等价的,因此项链可以从平面中拿起并翻转。由 n 个珠子组成的这种项链的数量 N^'(n,a),每颗珠子有 a 种可能的颜色,由下式给出

 N^'(n,a)=1/(2n){sum_(i=1)^(nu(n))phi(d_i)a^(n/d_i)+na^((n+1)/2)   for n odd; sum_(i=1)^(nu(n))phi(d_i)a^(n/d_i)+1/2n(1+a)a^(n/2)   for n even.
(2)

对于 a=2n=p奇素数,这可以简化为

 N^'(p,2)=(2^(p-1)-1)/p+2^((p-1)/2)+1.
(3)
NecklaceMirror

下面是一个 a=2a=3 的前几个项链数量的表格。请注意,对于 n>=6N(n,2) 大于 N^'(n,2)。对于 n=6,项链 110100 与其镜像 001011 不等价,这解释了 N(6,2)N^'(6,2) 之间差值为 1 的原因。类似地,两条项链 0010110 和 0101110 与其反转不等价,这解释了 N(7,2)N^'(7,2) 之间差值为 2 的原因。

nN(n,2)N^'(n,2)N^'(n,3)
斯隆A000031A000029A027671
1223
2336
34410
46621
58839
6141392
72018198
83630498
960461219
10108783210
111881268418
1235222422913
1363238062415
141182687173088
1521921224481598

Ball 和 Coxeter (1987) 考虑了找到 n 个人在一个环中的不同排列数量的问题,使得没有人两次或多次拥有相同的两个邻居。对于 8 个人,有 21 种这样的排列。


另请参阅

安托万项链, 德布鲁因序列, 固定, 自由, 不可约多项式, 约瑟夫问题, 林登词

使用 探索

参考文献

Ball, W. W. R. 和 Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 49-50, 1987.Dudeney, H. E. Problem 275 in 536 Puzzles & Curious Problems. New York: Scribner, 1967.Gardner, M. Martin Gardner's New Mathematical Diversions from Scientific American. New York: Simon and Schuster, pp. 240-246, 1966.Gilbert, E. N. 和 Riordan, J. "Symmetry Types of Periodic Sequences." Illinois J. Math. 5, 657-665, 1961.Riordan, J. "The Combinatorial Significance of a Theorem of Pólya." J. SIAM 4, 232-234, 1957.Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, p. 162, 1980.Ruskey, F. "关于项链、林登词、德布鲁因序列的信息。" http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html.Skiena, S. "Polya's Theory of Counting." §1.2.6 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 25-26, 1990.Sloane, N. J. A. Sequences A000029/M0563, A000031/M0564, A001869/M3860, and A027671 in "The On-Line Encyclopedia of Integer Sequences."

在 中被引用

项链

请引用为

Weisstein, Eric W. "项链。" 来自 Web 资源。 https://mathworld.net.cn/Necklace.html

主题分类