維基百科

多格骨牌

多格骨牌（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格骨牌中有些骨牌的中間有空洞，因此也無解。

12個五格骨牌形成一個8×8平方，刪除中間的2x2平方
35個六格骨牌（兩面），不考慮對稱相同則有60個片面骨牌。[1] 不同顏色代表不同對稱性類型。
94個六格骨牌的密鋪

列表 編輯

 
7種片面四格骨牌（  = 4）
 
12種両面五格骨牌（  = 5）。每個骨牌使用一個拉丁字母的字母。

多格骨牌有三種，以對稱分類：

  1. 自由（兩面）骨牌（剛體）：平移、轉動、反射、Glide reflection（英語：Glide reflection）；可以包括洞以及單連通（無洞）的骨牌
  2. 一片面：平移、轉動（不可反射）
  3. 固定（有向）：平移（不可轉動、不可反射）
  名稱 兩面（自由）[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]

但是有證明表示A為指數增長[8][9]（ ）

 

密鋪 編輯

這些問題有些是NP完全的，或與遞歸集合有關。

平面 編輯

任何少於或等於六格的骨牌都可以鋪滿整個平面，因為它們都滿足康威準則，而在全部108種七格骨牌中，有101種滿足康威準則，有104種可以鋪滿整個平面，另外4種（包括唯一一個中間有洞的那種）無法鋪滿整個平面，至於369種八格骨牌則有320種滿足康威準則，有343種可以鋪滿整個平面；1285種九格骨牌中則有960種滿足康威準則，有1050種可以鋪滿整個平面。

長方形 編輯

 
L骨牌有次數2

若需要至少n個多格骨牌P覆蓋任何長方形（或矩形的格子），則n是P的次數（order）。若一個多格骨牌不可以覆蓋（如Z形的四格骨牌），則其次數是未定義的。[11][1][12]

 
可以使用11個六格骨牌密鋪長方形

L形骨牌有次數2。[13]

次數 的骨牌存在（n是整數）。[12]

次數3的骨牌不存在。[14][12]

未解決的數學問題：奇數次數的多格骨牌存在嗎？
 

可不可以使用5、7或9個骨牌密鋪一個長方形這個問題仍未解答。有次數2的骨牌P，可以使用11個P覆蓋一個更大的長方形。[15][1][12]

更大奇數次數的骨牌存在。[16][17]

截至2020年，有兩個未解決的問題：

  • 奇數次數的多格骨牌存在嗎？
  • 若可以用n個骨牌密鋪一個長方形，且n是奇數，最小的n為何？現在已知n最多為11。
未解決的數學問題：若可以用n個骨牌密鋪一個長方形，且n是奇數，最小的n為何？現在已知n最多為11。
 

謎題和遊戲 編輯

最小面積 編輯

若可以用骨牌A覆蓋每個n格骨牌，則A是共同超形式（common superform、CS）。若A是共同超形式中面積最小的那個，則A是最小共同超形式（minimal common superform、MCS）。比如，五格骨牌的MCS是下面兩個九格骨牌。無論P是哪一個五格骨牌，P都可以放在這兩個骨牌裡。[1][12][18]

  ###     ###
#####    #####
  #       #

參見 編輯

參考文獻 編輯

  1. ^ 1.0 1.1 1.2 1.3 Golomb, Golomb. Polyominoes. 1975. 
  2. ^ （OEIS數列A000105）
  3. ^ （OEIS數列A000988）
  4. ^ （OEIS數列A001168）
  5. ^ Jensen, Iwan. Enumerations of Lattice Animals and Trees. Journal of Statistical Physics. 2001, 102 (3/4): 865–881. doi:10.1023/A:1004855020556. 
  6. ^ 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. 
  7. ^ 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. 
  8. ^ 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= (幫助)
  9. ^ 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 （英語）. 
  10. ^ 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） （英語）. 
  11. ^ Tiling Rectangles With Polyominoes. www.eklhad.net. [2020-02-15]. （原始內容存檔於2020-02-15）. 
  12. ^ 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=為空 (幫助)
  13. ^ Weisstein, Eric W. (編). L-Polyomino. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2020-02-15]. （原始內容存檔於2015-07-26） （英語）. 
  14. ^ 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） （英語）. 
  15. ^ Primes of the P hexomino. www.cflmath.com. [2020-02-15]. （原始內容存檔於2016-03-22）. 
  16. ^ Tiling Rectangles and Half Strips with Congruent Polyominoes. www.cflmath.com. [2020-02-15]. （原始內容存檔於2020-01-15）. 
  17. ^ co.combinatorics - Cutting a rectangle into an odd number of congruent pieces. MathOverflow. [2020-02-15]. （原始內容存檔於2020-02-15）. 
  18. ^ Polyomino Common Superforms. puzzlezapper.com. [2020-02-15]. （原始內容存檔於2017-05-21）. 
  19. ^ Whittington, S. G.; Soteros, C. E. (1990)., Whittington, S. G.; Soteros, C. E. (1990). "Lattice Animals: Rigorous Results and Wild Guesses".. 
  20. ^ In Grimmett, G.; Welsh, D. (eds.)., In Grimmett, G.; Welsh, D. (eds.). Disorder in Physical Systems. Oxford University Press.. 


取自「https://zh.wikipedia.org/w/index.php?title=多格骨牌&oldid=74738961」