ドミノタイリングのソースを表示

{{要改訳}}
[[Image:Pavage domino.svg|thumb|right|四方形のドミノタイリング]]

[[ユークリッド空間|ユークリッド平面]]上のある領域の'''ドミノタイリング'''(domino tiling)とは、右の図のように[[ドミノ]]で領域を[[平面充填|埋め尽す]]ことである。同じことであるが、ドミノタイリングは、各々のドミノの中心に頂点として隣合うドミノの 2つの頂点を結ぶことで形成される{{仮リンク|格子グラフ|en|grid graph}}(grid graph)の[[マッチング (グラフ理論)|マッチング]]のことでもある。[[モノマー]]、ダイマー、[[ポリマー]]と呼ぶように、2つの原子が繋がったという意味であるユークリッド平面上の（あるいは、[[トーラス]] <math>\mathbb{R}^2/\mathbb{Z}^2</math> 上の）'''ダイマーモデル'''（Dimer model，双体模型）は、{{仮リンク|多角形分割|en|polygon division}}(polygon division)をもたらすモデルであり、[[マッチング (グラフ理論)|完全マッチング]]であるダイマーモデルは、ドミノタイリングと同義である。

== 高さ函数 ==
2次元の正方形の格子上のタイリングのクラスに対し、格子のノードへ整数を割り当てる高さ函数を定義することができる。例えば、チェスボード（格子を黒と白の市松模様とする）を描いて、高さ 0 を持つノード <math>A_0</math> を固定すると、どのノードに対しても <math>A_0</math> からの経路が存在する。この経路上で、各々のノード <math>A_{n+1}</math> (つまり、四方形の頂点）の高さを、<math>A_n</math> から <math>A_{n+1}</math> への経路の右側の四方形が黒であれば、前のノード <math>A_n</math> に 1 をプラスした値とする。そうでなければ、1 をマイナスした値とする。

さらに詳しくは、{{harvtxt|Kenyon|Okounkov|2005}}に記載がある。

==サーストンの高さ条件==
[[ウィリアム・サーストン]](William Thurston)は、1990年に平面内の単連結な領域が、単位四方形の組（ドミノ）によりドミノタイリングとして形成されるか否かを決定できることを著した。彼は、3次元の{{仮リンク|整数格子|en|integer lattice}}(integer lattice)の中の点 (''x'',''y'',''z'') を頂点として持つような[[グラフ理論#無向グラフ|無向グラフ]]を作った。そこでは各々の点が 4つの近傍に連結していて、''x''+''y'' が偶数であれば、(''x'',''y'',''z'') は (''x''+1,''y'',''z''+1), (''x''-1,''y'',''z''+1), (''x'',''y''+1,''z''-1), (''x'',''y''-1,''z''-1) と連結し、一方、''x''+''y'' が奇数であれば、(''x'',''y'',''z'') は (''x''+1,''y'',''z''-1), (''x''-1,''y'',''z''-1), (''x'',''y''+1,''z''+1), (''x'',''y''-1,''z''+1) と連結している。この領域の境界は、(''x'',''y'') 平面の中の整数の点の列として見なすと、この一意に {{仮リンク|3次元グラフ|en|three-dimensional graph}}(three-dimensional graph)の中の経路へ（一度、初期の高さを決めると）持ち上げることができる。この領域がタイリング可能であるための必要条件は、この経路が 3次元で単純な閉曲線を形成することを除いて閉じている必要がある。しかし、この条件だけでは充分でない。境界の経路のより注意深く解析して、サーストンは必要かつ充分な領域のタイリングの可能性の判定条件を与えた。

==領域のタイリングの数==
[[Image:Dominoes tiling 8x8.svg|thumb|right|8×8 マスのドミノタイリングで、ドミノの長辺と長辺が接するペアの数が最小となるもの（中央に一組ある）。この並べ方は、8×8 マスでの[[畳]]の敷き詰め方としても有効であり、内部のどの点も4つのドミノが接することがない。]]

<math> m \times n </math> の長方形を <math> \frac{mn}{2} </math> 個のドミノで埋め尽くす方法が何通りあるかの個数の公式は、独立に、{{harvtxt|Temperley|Fisher|1961}} と {{harvtxt|Kasteleyn|1961}} により計算され、

:<math> \prod_{j=1}^{\lceil\frac{m}{2}\rceil} \prod_{k=1}^{\lceil\frac{n}{2}\rceil} \left ( 4\cos^2 \frac{\pi j}{m + 1} + 4\cos^2 \frac{\pi k}{n + 1} \right )</math>

として得られた。

この特別な場合として、<math>2\times n</math>-長方形のタイリングの方法が何通りあるかという問題がある。この数は、[[フィボナッチ数|フィボナッチ数列]]の ''n''-番目の数である{{OEIS|id=A000045}} {{harv|Klarner|Pollack|1980}}。

他の特別な場合として、''m'' = ''n'' = 0, 2, 4, 6, 8, 10, 12, ...  であるようなケースがある。
:1, 2, 36, 6728, 12988816, 258584046368, 53060477521960000, ... {{OEIS|id=A004003}}.

これらの何通りあるかという数は、[[固有値]]が明確に分かる <math>mn \times mn</math> 個の[[交代行列]]の[[パフィアン]]として記述することにより、計算することが可能となる。このテクニックは多くの数学的に関連する問題へ適用することが可能である。例えば、[[統計力学]]での{{仮リンク|ダイマー-ダイマー相関函数|en|dimer-dimer correlator function}}(dimer-dimer correlator function)の古典的 2次元の計算がある。

領域のタイリングの数は境界条件に対して非常に敏感で、一見たいしたことのない形の変化であっても、その数が劇的に変化する場合がある。わかりやすい例に、位数 ''n'' の{{仮リンク|アステカダイアモンド|en|Aztec diamond}}(Aztec diamond) があり、このタイリングの数は、2<sup>(''n''&nbsp;+&nbsp;1)''n''/2</sup> である。一方、位数が同じ ''n'' でも、中央の長い列が2列ではなく3列に '''拡張されたアステカダイアモンド''' になると、タイリングの数は''n'' の[[テトレーション]]から大きく減少し、指数的な数である{{仮リンク|デラノイ数|en|Delannoy number}}(Delannoy number) D(''n'',''n'') に等しくなる。また、中央列が1列である '''縮小されたアステカダイアモンド'''は、たったひとつのタイリングしか持たない。
<gallery>
File:Diamant azteque.svg|位数 4 のアステカダイアモンド、1024 種類のドミノタイリングを持つ
File:Diamant azteque plein.svg|位数 4 のアステカダイアモンドにおけるドミノタイリングの一例
</gallery>

==参照項目==

*[[統計力学]]
*{{仮リンク|ガウス自由場|en|Gaussian free field}}(Gaussian free field)、一般的な状況下で、高さ函数のスケール極限（つまり、大きなアステカダイアモンドの内接円板の内部）
*{{仮リンク|多重チェスボート問題|en|Mutilated chessboard problem}}(Mutilated chessboard problem)、チェスボートの 62個の正方形のドミノタイリングに関するパズル
*[[畳]]、日本式の部屋の床のタイリングに使われるドミノの形をした床のマット、並べ方にあるルールを持っている。

== 参考文献 ==
* {{Citation | last1=Bodini | first1=Olivier | last2=Latapy | first2=Matthieu | title=Generalized Tilings with Height Functions | url=http://www-rp.lip6.fr/%7Elatapy/Publis/morfismos03.pdf | year=2003 | journal=Morfismos | issn=1870-6525 | volume=7 | issue=1 | pages=47–68}}.
* {{cite journal
|first1=F. | last1=Faase
|journal=Ars Combin.
|title=On the number of specific spanning subgraphs of the graphs G X P_n
|volume=49 | mr=1633083 | pages=129–154 | year=1998 }}
* {{cite journal
|first1=J. L. | last1=Hock
|first2=R. B. | last2=McQuistan
|title=A note on the occupational degeneracy for dimers on a saturated two-dimenisonal lattice space
|journal=Discrete Appl. Math.
|volume=8 | pages=101–104 | year=1984
|doi = 10.1016/0166-218X(84)90083-0 |mr=0739603 }}
*{{citation
 | title = The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice
 | journal = [[:en:Physica (journal)|Physica]]
 | volume = 27 | issue = 12 | year = 1961 | pages = 1209–1225
 | first = P. W. | last = Kasteleyn | bibcode=1961Phy....27.1209K
 | doi = 10.1016/0031-8914(61)90063-5}}.
*{{Citation | last1=Kenyon | first1=Richard | mr=1798998 | zbl=1026.82007 | year=2000 | volume=13 | chapter=The planar dimer model with boundary: a survey | pages=307–328 | editor1-last=Baake | editor1-first=Michael | editor2-last=Moody | editor2-first=Robert V. | editor2-link=Robert Moody | title=Directions in mathematical quasicrystals | location=Providence, RI | publisher=[[American Mathematical Society]] | series=CRM Monograph Series | isbn=0-8218-2629-8 }}
* {{Citation | last1=Kenyon | first1=Richard | last2=Okounkov | first2=Andrei | author2-link=Andrei Okounkov | title=What is … a dimer? | url=http://www.ams.org/notices/200503/what-is.pdf | year=2005 | journal=[[Notices of the American Mathematical Society]] | issn=0002-9920 | volume=52 | issue=3 | pages=342–343}}.
*{{citation
 | last1 = Klarner | first1 = David
 | last2 = Pollack | first2 = Jordan
 | doi = 10.1016/0012-365X(80)90098-9
 | issue = 1
 | journal = [[:en:Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 588907 | zbl=0444.05009
 | pages = 45–52
 | title = Domino tilings of rectangles with fixed width
 | volume = 32
 | year = 1980}}.
*{{cite arXiv| first1=Richard J. | last1=Mathar | eprint=1311.6135
|year=2013 | title=Paving rectangular regions with rectangular tiles: tatami and non-tatami tilings}}
*{{citation
 | first=James | last=Propp | authorlink = Jim Propp
 | title=Lambda-determinants and domino-tilings
 | journal = Advances in Applied Mathematics
 | volume = 34 | issue = 4 | year = 2005 | pages = 871–879
 | doi = 10.1016/j.aam.2004.06.005
 | arxiv=math.CO/0406301}}.
* {{cite journal | first1=Frank | last1=Ruskey
|first2=Jennifer | last2=Woodcock
|title = Counting fixed-height Tatami tilings
|journal=Electron. J. Combin | volume=16 | number=1 
|page=R126 | mr=2558263 | year=2009 }}
*{{citation
 | title = Domino tilings and products of Fibonacci and Pell numbers
 | journal = Journal of Integer Sequences
 | volume = 5
 | year = 2002 | issue = Article 02.1.2
 | url = http://www.emis.de/journals/JIS/VOL5/Sellers/sellers4.html
 | first = James A. | last = Sellers}}.
* {{cite journal
|first1=Richard P. | last1=Stanley
|title=On dimer coverings of rectangles of fixed width
|journal=Discrete Appl. Math
|volume=12 | pages=81–87 | mr=0798013 | year=1985 | doi=10.1016/0166-218x(85)90042-3}}
*{{citation
 | authorlink = William Thurston | last = Thurston | first = W. P.
 | title = Conway's tiling groups
 | journal = American Mathematical Monthly
 | volume = 97
 | issue = 8
 | year = 1990
 | pages = 757–773
 | doi = 10.2307/2324578
 | publisher = Mathematical Association of America
 | jstor = 2324578}}.
*{{citation
 | title = The Penguin Dictionary of Curious and Interesting Numbers
 | edition = revised | year = 1997 | isbn = 0-14-026149-4 | page = 182
 | last = Wells | first = David
 | publisher = Penguin
 | location = London}}.
* 高崎金久『線形代数と数え上げ』[[日本評論社]] (2012) ISBN 978-4535786806
<!--
{{Tessellation}}
-->
{{DEFAULTSORT:とみのたいりんく}}
[[Category:統計力学]]
[[Category:格子模型]]
[[Category:組合せ論]]
[[Category:数学パズル]]
[[Category:数学に関する記事]]