主題
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.tw/Necklace.html

主題分類