ドミノ（数学）

数学において、ドミノは2次のポリオミノ、つまり、端から端まで接続された2つの同じサイズの正方形で構成される平面上の多角形です。 ^[1]回転と反射を異なる形状と見なさない場合、自由なドミノは1つだけです。

反射対称性があるため、反射が異なるとみなされる唯一の片面ドミノでもあります。回転も異なるとみなされる場合、2つの固定ドミノがあります。2つ目のドミノは、上のドミノを90°回転させることによって作成できます。^[2]^[3]

より広い意味では、ドミノという用語は、あらゆる形状のタイルを意味すると理解されることもあります。 ^[4]

梱包とタイル張り

ドミノは、平面を数え切れないほど多くの方法で並べることができます。2× nの長方形をドミノで並べる方法は個あり、これはn番目のフィボナッチ数です。^[5] $F_{n}$

ドミノのタイル張りは、いくつかの有名な問題に登場します。アステカのダイヤモンド問題では、大きなダイヤモンド形の領域に2の累乗に等しい数のタイル張りがあり、^[6]ほとんどのタイル張りは中央の円形領域内でランダムに表示され、この「北極圏」の外側ではより規則的な構造を持ちます。また、チェス盤から2つの反対側の角を削除するとドミノでタイルを張ることができなくなる、切断されたチェス盤問題もあります。 ^[7]

^ ゴロム、ソロモン W. (1994)。ポリオミノ（第 2 版）。プリンストン、ニュージャージー：プリンストン大学出版局。ISBN 0-691-02444-8。
^ Weisstein, Eric W. 「Domino」。MathWorld – Wolfram Web リソースより。2009 年 12 月 5 日閲覧。
^ Redelmeier, D. Hugh (1981). 「ポリオミノの数え方：もう一つの攻撃」.離散数学. 36 (2): 191–203. doi : 10.1016/0012-365X(81)90237-5 .
^ Berger, Robert (1966). 「ドミノ問題の決定不可能性」Memoirs Am. Math. Soc . 66 .
^具体的な数学、 Wayback Machineで2020年11月6日にアーカイブ、 Graham、Knuth、Patashnik著、Addison-Wesley、1994年、320ページ、ISBN 0-201-55802-5
^ エルキーズ、ノアム;クーパーバーグ、グレッグ;ラーセン、マイケル;プロップ、ジェームズ(1992)、「交互符号行列とドミノタイル。I」、代数的組合せ論ジャーナル、1 (2): 111–132、doi : 10.1023/A:1022420103267、MR 1226347
^ メンデルソン、NS (2004)、「ドミノによるタイル張り」、大学数学ジャーナル、35 (2)、アメリカ数学協会: 115–120、doi :10.2307/4146865、JSTOR 4146865。