多格骨牌
此條目目前正依照其他維基百科上的內容進行翻譯。 (2020年2月15日) |
多格骨牌(Polyomino),又稱多連塊、多連方、多方塊或多連方塊,是由全等正方形連成的圖形,包括四格骨牌、五格骨牌、六格骨牌等,n格骨牌的個數為(鏡射或旋轉視作同一種):
- 1, 1, 1, 2, 5, 12, 35, 108, 369, 1285, 4655, 17073, 63600, 238591, 901971, 3426576, 13079255, 50107909, 192622052, 742624232, 2870671950, ... (OEIS數列A000105)
除了n=0, 1, 2的顯然易見的條件以外,只有n=5的時候才能用所有的n格骨牌填滿一個長方形(見五格骨牌#長方形填充),n=3的情形顯然無解,對n=4和n=6無解的證明需要使用肢解國際象棋盤問題的概念,而時,n格骨牌中有些骨牌的中間有空洞,因此也無解。
列表
多格骨牌有三種,以對稱分類:
名稱 | 兩面(自由)[2] | 片面(單邊)[3] | 有向(固定)[4] | |
---|---|---|---|---|
1 | 一格骨牌 | 1 | 1 | 1 |
2 | 二格骨牌 | 1 | 1 | 2 |
3 | 三格骨牌 | 2 | 2 | 6 |
4 | 四格骨牌 | 5 | 7 | 19 |
5 | 五格骨牌 | 12 | 18 | 63 |
6 | 六格骨牌 | 35 | 60 | 216 |
7 | 七格骨牌 | 108 | 196 | 760 |
8 | 八格骨牌 | 369 | 704 | 2725 |
9 | 九格骨牌 | 1285 | 2500 | 9910 |
10 | 十格骨牌 | 4655 | 9189 | 36446 |
11 | 十一格骨牌 | 17073 | 33896 | 135268 |
12 | 十二格骨牌 | 63600 | 126759 | 505861 |
13 | 十三格骨牌 | 238591 | 476270 | 1903890 |
14 | 十四格骨牌 | 901971 | 1802312 | 7204874 |
15 | 十五格骨牌 | 3426576 | 6849777 | 27394666 |
計算算法
若A(n)是自由n格骨牌的總數,則有猜想說明
其中 。但是這個是未解決的問題,缺乏證明。[7]
密鋪
平面
任何少於或等於六格的骨牌都可以鋪滿整個平面,因為它們都滿足康威準則,而在全部108種七格骨牌中,有101種滿足康威準則,有104種可以鋪滿整個平面,另外4種(包括唯一一個中間有洞的那種)無法鋪滿整個平面,至於369種八格骨牌則有320種滿足康威準則,有343種可以鋪滿整個平面;1285種九格骨牌中則有960種滿足康威準則,有1050種可以鋪滿整個平面。
長方形
若需要至少n個多格骨牌P覆蓋任何長方形(或矩形的格子),則n是P的次數(order)。若一個多格骨牌不可以覆蓋(如Z形的四格骨牌),則其次數是未定義的。[11][1][12]
L形骨牌有次數2。[13]
可不可以使用5、7或9個骨牌密鋪一個長方形這個問題仍未解答。有次數2的骨牌P,可以使用11個P覆蓋一個更大的長方形。[15][1][12]
截至2020年,有兩個未解決的問題:
- 奇數次數的多格骨牌存在嗎?
- 若可以用n個骨牌密鋪一個長方形,且n是奇數,最小的n為何?現在已知n最多為11。
謎題和遊戲
最小面積
若可以用骨牌A覆蓋每個n格骨牌,則A是共同超形式(common superform、CS)。若A是共同超形式中面積最小的那個,則A是最小共同超形式(minimal common superform、MCS)。比如,五格骨牌的MCS是下面兩個九格骨牌。無論P是哪一個五格骨牌,P都可以放在這兩個骨牌裏。[1][12][18]
### ### ##### ##### # #
參見
參考文獻
- ^ 1.0 1.1 1.2 1.3 Golomb, Golomb. Polyominoes. 1975.
- ^ (OEIS數列A000105)
- ^ (OEIS數列A000988)
- ^ (OEIS數列A001168)
- ^ Jensen, Iwan. Enumerations of Lattice Animals and Trees. Journal of Statistical Physics. 2001, 102 (3/4): 865–881. doi:10.1023/A:1004855020556.
- ^ Conway, A. Enumerating 2D percolation series by the finite-lattice method: theory. Journal of Physics A: Mathematical and General. 1995-01-21, 28 (2): 335–349. ISSN 0305-4470. doi:10.1088/0305-4470/28/2/011.
- ^ Jensen, Iwan; Guttmann, Anthony J. Statistics of lattice animals (polyominoes) and polygons. Journal of Physics A: Mathematical and General. 2000-07-28, 33 (29): L257–L263. ISSN 0305-4470. doi:10.1088/0305-4470/33/29/102.
- ^ Barequet Gill, Rote Günter; ShalahMira. λ > 4: an improved lower bound on the growth constant of polyominoes. Communications of the ACM. 2016-06-24 [2020-02-15]. doi:10.1145/2851485. (原始內容存檔於2020-06-30) (英語). Authors list列表缺少
|last2=
(幫助) - ^ Klarner, D. A.; Rivest, R. L. A Procedure for Improving the Upper Bound for the Number of n -Ominoes. Canadian Journal of Mathematics. 1973-06, 25 (3): 585–602. ISSN 0008-414X. doi:10.4153/CJM-1973-060-4 (英語).
- ^ Golomb, Solomon W. Tiling with sets of polyominoes. Journal of Combinatorial Theory. 1970-07, 9 (1): 60–71 [2020-02-15]. doi:10.1016/S0021-9800(70)80055-2. (原始內容存檔於2021-02-26) (英語).
- ^ Tiling Rectangles With Polyominoes. www.eklhad.net. [2020-02-15]. (原始內容存檔於2020-02-15).
- ^ 12.0 12.1 12.2 12.3 12.4 Golomb, Solomon W. (Solomon Wolf). Polyominoes : puzzles, patterns, problems, and packings. 2nd ed. Princeton, N.J.: Princeton University Press https://www.worldcat.org/oclc/29358809. 1994. ISBN 0-691-08573-0. OCLC 29358809. 缺少或
|title=
為空 (幫助) - ^ Weisstein, Eric W. (編). L-Polyomino. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2020-02-15]. (原始內容存檔於2015-07-26) (英語).
- ^ Stewart, I. N; Wormstein, A. Polyominoes of order 3 do not exist. Journal of Combinatorial Theory, Series A. 1992-09-01, 61 (1): 130–136 [2020-02-15]. ISSN 0097-3165. doi:10.1016/0097-3165(92)90058-3. (原始內容存檔於2020-01-12) (英語).
- ^ Primes of the P hexomino. www.cflmath.com. [2020-02-15]. (原始內容存檔於2016-03-22).
- ^ Tiling Rectangles and Half Strips with Congruent Polyominoes. www.cflmath.com. [2020-02-15]. (原始內容存檔於2020-01-15).
- ^ co.combinatorics - Cutting a rectangle into an odd number of congruent pieces. MathOverflow. [2020-02-15]. (原始內容存檔於2020-02-15).
- ^ Polyomino Common Superforms. puzzlezapper.com. [2020-02-15]. (原始內容存檔於2017-05-21).
- ^ Whittington, S. G.; Soteros, C. E. (1990)., Whittington, S. G.; Soteros, C. E. (1990). "Lattice Animals: Rigorous Results and Wild Guesses"..
- ^ In Grimmett, G.; Welsh, D. (eds.)., In Grimmett, G.; Welsh, D. (eds.). Disorder in Physical Systems. Oxford University Press..