主題
Search

Steiner 三元系


X 為一個包含 v>=3 個元素的集合,BX 的 3-子集(三元組)的集合,使得 X 的每個 2-子集B恰好一個 三元組中出現。那麼 B 稱為 Steiner 三元系,是 Steiner 系 的一個特殊情況,其中 t=2k=3。階為 v 的 Steiner 三元系 S(v)=S(v,k=3,lambda=1) 存在的當且僅當 v=1,3 (mod 6) (Kirkman 1847)。此外,如果階為 v_1v_2 的 Steiner 三元系 S_1S_2 存在,那麼階為 v_1v_2 的 Steiner 三元系 S 也存在 (Ryser 1963, p. 101)。

SteinerTripleSystemS9

階為 v 的小階 Steiner 三元系 S(v) 的例子有:

S_3={{1,2,3}}
(1)
S_7={{1,2,4},{2,3,5},{3,4,6},{4,5,7},{5,6,1},{6,7,2},{7,1,3}}
(2)
S_9={{1,2,3},{4,5,6},{7,8,9},{1,4,7},{2,5,8},{3,6,9},{1,5,9},{2,6,7},{3,4,8},{1,6,8},{2,4,9},{3,5,7}}.
(3)

Steiner 三元系 S_9 如上圖所示。

階為 v=7, 9, 13, 15, 19, ... (即,6k+1,3)的非同構 Steiner 三元系 S(v) 的數量分別為 1, 1, 2, 80, 11084874829, ... (Stinson and Ferch 1985; Colbourn and Dinitz 1996, pp. 14-15; Kaski and Östergård 2004; OEIS A030129)。S(7) 與階為 2 的有限射影平面相同。S(9) 是一個有限仿射平面,可以從以下陣列構造:

 a b c; d e f; g h i.
(4)

兩個 S(13)s 之一是有限雙曲平面。Tonchev 和 Weishaar (1997) 研究了 80 個 Steiner 三元系 S(15)


參見

Hadamard 矩陣, Kirkman 三元系, 社交高爾夫球手問題, Steiner 四元系, Steiner 系

使用 探索

參考文獻

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 107-109 and 274, 1987.Colbourn, C. J. and Dinitz, J. H. (Eds.). "Steiner Triple Systems." §4.5 in CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, pp. 14-15 and 70, 1996.Gardner, M. "Mathematical Games: On the Remarkable Császár Polyhedron and Its Applications in Problem Solving." Sci. Amer. 232, 102-107, May 1975.Kaski, P. and Östergård, P. R. J. "The Steiner Triple Systems of Order 19." Math. Comput. 73, 2075-2092, 2004.Kaski, P.; Östergård, P. R. J.; Topalova, S.; and Zlatarski, R. "Steiner Triple Systems of Order 19 and 21 with Subsystems of Order 7." http://www.tcs.hut.fi/~pkaski/19and21.ps.Kirkman, T. P. "On a Problem in Combinatorics." Cambridge Dublin Math. J. 2, 191-204, 1847.Lindner, C. C. and Rodger, C. A. Design Theory. Boca Raton, FL: CRC Press, 1997.Ryser, H. J. Combinatorial Mathematics. Buffalo, NY: Math. Assoc. Amer., pp. 99-102, 1963.Sloane, N. J. A. Sequence A030129 in "The On-Line Encyclopedia of Integer Sequences."Stinson, D. R. and Ferch, H. "2000000 Steiner Triple Systems of Order 19." Math. Comput. 44, 533-535, 1985.Tonchev, V. D. and Weishaar, R. S. "Steiner Triple Systems of Order 15 and Their Codes." J. Stat. Plan. Inference 58, 207-216, 1997.

在 中被引用

Steiner 三元系

請引用本文為

Weisstein, Eric W. "Steiner 三元系。" 出自 Web 資源。 https://mathworld.tw/SteinerTripleSystem.html

主題分類