多格骨牌

多格骨牌（Polyomino），又称多连块、多连方、多方块或多连方块，是由全等正方形连成的图形，包括四格骨牌，五格骨牌和六格骨牌等等，n格骨牌的个数为：（镜射或旋转视作同一种）

除了n=0, 1, 2的显然条件以外，只有n=5的时候才能用所有的n格骨牌填满一个长方形（见五格骨牌#长方形填充），n=3的情形显然无解，对n=4跟n=6无解的证明要用到肢解国际象棋盘问题的概念，而${\displaystyle n\ge <!--\; \ge \; -->7}$则是n格骨牌中有些是中间有空洞的，因此也无解。

有三种多格骨牌，使用对称性分类：

若A(n)是自由n格骨牌的总数，有人猜想

${\displaystyle A_n\sim <!--\; \sim \; -->c{\mathrm{\lambda <!--\; \lambda \; -->}}^n/n}$

其中${\displaystyle c\approx <!--\; \approx \; -->0.3169,\mathrm{\lambda <!--\; \lambda \; -->}\approx <!--\; \approx \; -->4.0626}$。但是这个是未解决的问题，缺乏证明。

但是有人证明A表示指数增长（）

${\displaystyle \underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}(A_n{)}^{1/n}=\mathrm{\lambda <!--\; \lambda \; -->}}$

这也许是普遍性的极限。

有时候这些问题是NP完全的，或者跟递归集合有关。

任何少于或等于六格的骨牌都可以铺满整个平面，因为都满足康威准则，而全部108种七格骨牌当中，有101种满足康威准则，而有104种可以铺满整个平面，另外4种（包括唯一一个中间有洞的那种）是没办法铺满整个平面的，至于369种八格骨牌则有320种满足康威准则，343种可以铺满整个平面，1285种九格骨牌则有960种满足康威准则，1050种可以铺满整个平面。

若需要至少n把多格骨牌P覆盖任何长方形（或长方形的格子），则n是P的次数（order）。若不可以覆盖（例如Z形的四格骨牌），次数是未定义的。

L形骨牌有次数2。

次数${\displaystyle 4n}$的骨牌存在（n是整数）。

次数3 的骨牌不存在。

不知道可以使用5、7、9把骨牌密铺一个长方形。有次数2的骨牌P，可以使用11把P覆盖一个更大的长方形。

更大奇数次数的骨牌存在。

但是截至2020年，有两个未解决的问题：

若可以用骨牌A覆盖每把n格骨牌，则A是共同超形式（common superform、CS）。若A有最小的面积，则A是最小共同超形式（minimal common superform、MCS）。比方说，五格骨牌的MCS是下面两把九格骨牌。无论P是哪一把五格骨牌，P都可以放在这两把骨牌。

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

参见

• 多连立方体
• 渗流理论
• 杨表
• 角斗士棋
• 多格形（polyform）

参考文献

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.  |author=和|last=只需其一 (帮助)
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. doi:10.1145/2851485 （英语）.  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. doi:10.1016/S0021-9800(70)80055-2 （英语）. 
11. ^ Tiling Rectangles With Polyominoes. www.eklhad.net. . 
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=为空 (帮助) 引文格式1维护：冗余文本 (link)
13. ^ Weisstein, Eric W. L-Polyomino. mathworld.wolfram.com. （英语）. 
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. ISSN 0097-3165. doi:10.1016/0097-3165(92)90058-3 （英语）. 
15. ^ Primes of the P hexomino. www.cflmath.com. . 
16. ^ Tiling Rectangles and Half Strips with Congruent Polyominoes. www.cflmath.com. . 
17. ^ co.combinatorics - Cutting a rectangle into an odd number of congruent pieces. MathOverflow. . 
18. ^ Polyomino Common Superforms. puzzlezapper.com. . 
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..