9
大学数学基礎解説
文献あり

アステカダイヤモンドの敷き詰め

466
0

はじめに

位数nのアステカダイヤモンドとは, 領域|x|+|y|n+1に含まれる1×1の正方形の合併のことをいいます. これを1×2の長方形(ドミノ)で敷き詰めていくことを考えます.
位数!FORMULA[4][36584004][0]のアステカダイヤモンド 位数n=3のアステカダイヤモンド
ドミノで敷き詰め ドミノで敷き詰め
実は, 位数nのアステカダイヤモンドをドミノで敷き詰める方法の総数は2n(n+1)2通りであることが知られています. シンプルで綺麗な結果ですね!今回はこの記事でその証明をしていきたいと思います.

証明の方針

①とある経路とドミノでの敷き詰めを一対一対応させる
②一対一対応させた経路の数を数え上げる

証明

①一対一対応

ドミノ経路

与えられたドミノでの敷き詰めを, 経路(の組)に変換することを考えます. 具体的には、次のようにします:

1.図3のように, アステカダイヤモンドの下半分の部分のうち, 左側の辺すべてに点をつける(これらを始点とする経路を描く).
2.図4のような方法で, 右側の辺に到達するまで矢印を引く.

先ほどの敷き詰めの例を使うと, 図5のような経路を得ることが出来ます.

始点 始点
矢印の引きかた 矢印の引きかた
経路の例 経路の例

さらに, アステカダイヤモンドを図6のように市松模様で塗り分けると, 経路上の点は全て色付きのマスの左側の辺(=白いマスの右側の辺)の上にのっていることが分かります.
市松模様 市松模様

加えて, これらの経路は決して交差しないことが分かります. (ふたつの経路が交差するとは, 経路が同じ点を共有することをいいます. 交差すると仮定すると, 図7の示すいずれかの状況になる必要がありますが, それはどれも不可能です. )

このようにはならない このようにはならない

経路ドミノ

逆に, アステカダイヤモンドに対して

・始点を図3のように定め
x方向, y方向への移動がそれぞれ(x,y)=(1,1),(2,0),(1,1)のいずれかになるように
・経路同士が交差しないように

経路を書き込むと, その経路から一意にドミノの敷き詰めを定めることができます.

証明

まず, 経路は交差しないので, 書き込んだ経路が通るマスにはドミノを一意に敷き詰めることができます. したがって, 経路が書き込まれていないマスにドミノを一意に敷き詰められることが言えればいいわけです. ここで, 経路が色付きのマスを通ることと経路がその一つ左の白いマスを通ることが(始点・終点以外の位置で)同値であることより, 経路が書き込まれていないマスは, 左が白いマスで右が色付きのマスである横倒しのドミノで敷き詰められることが分かります. これ以外のドミノを少なくともひとつ使って経路が通らないマスを敷き詰められたと仮定すると, そのドミノから図4のルールに従って左右に経路を伸ばしていけば, 結局このドミノはいずれかの経路に組み込まれてしまうことになり, 矛盾します.以上より経路からドミノの敷き詰めが一意に決まることが示されました.

以上より, 条件をみたす非交差経路の組の数を数える問題に帰着することができました!

②経路の数え上げ

非交差経路 非交差経路

図8のように, 最下段のマスを通るようにx軸を, 図形の左右の対称軸にy軸をとり, i=1,2,,nについて点AiおよびBiをそれぞれ(2i+1,0),(2i1,0)で定めます. ここで, AiからBiへ向かう経路であって

(i)x軸を下回らない
(ii)x方向、y方向への移動がそれぞれ(x,y)=(1,1),(2,0),(1,1)のいずれかである

の条件を満たす経路をπiとし, 非交差経路の組(π1,π2,,πn)全体の集合をΠnとすると, ①の考察より|Πn|が求めるべきものです. また, (0,0)から(2n,0)へ向かう経路であって, (i)と(ii)の条件をどちらも満たすものの総数をrnで表します(このrnをlarge Schröder numberと呼びます).

さらに, (i)と(ii)に加えて

(iii)x軸上で(x,y)=(2,0)の移動を行わない

の条件を満たしてAiからBiへ向かう経路をωiとし, 非交差経路(ω1,ω2,,ωn)全体の集合をΩnとします. また, (0,0)から(2n,0)へ向かう経路であって(i)(ii)(iii)の条件をすべて満たすものの総数をsnで表します(このsnをsmall Schröder numberと呼びます).

ここでいくつかの補題を用意します:

|Ωn+1|=|Πn|

!FORMULA[47][38352][0]軸を下げたところに取る x軸を下げたところに取る

図8における直線y=2を新たにx軸とし, 図9のように点をとって非交差経路を対応させると, これらはΩn+1そのものであることがわかる.

ij列目の成分がri+j1である行列
(r1r2rnr2r3rn+1rnrn+1r2n1)
Hn, ij列目の成分がsi+j1である行列
(s1s2sns2s3sn+1snsn+1s2n1)
Gnとすると,
|Πn|=det(Hn),|Ωn|=det(Gn)

LGV公式より従う. LGV公式については こちら を参照.

rn=2sn

(0,0)から(2n,0)へ向かう経路であって(i)(ii)の条件を満たすもののうち、(iii)をみたすものの個数と(iii)をみたさないものの個数が等しいことを示せばよい. これらの集合の間に次のように全単射を構成する:
(iii)をみたさない経路について, 左から見たときに最後に登場する(x,y)=(2,0)の移動をで表し, その左側の経路をP, 右側の経路をQとする. 与えられた経路"PQ""PQ"に対応させる写像を考えると, これは全単射である(,でそれぞれ(x,y)=(1,1),(1,1)の移動を表す). これは, (iii)をみたす経路について, 左から見たときに(始点を除いて)はじめてx軸上に点がのるまでの経路を"P"とみなして先ほどと逆の操作を行うことを考えれば分かる.

経路!FORMULA[75][1342216998][0] 経路"PQ"
経路!FORMULA[76][-204315566][0] 経路"PQ"
図ではPを赤色で, Qを青色で, 矢印部分を緑色で表している.

以上より|Πn|を求める準備が整いました!

|Πn|を求める

補題2と補題3より, Inを単位行列とすれば
|Πn|=det(Hn)=det(2InGn)=det(2In)det(Gn)=2n|Ωn|
が従うので, 補題1とあわせて
|Πn+1|=2n+1|Ωn+1|=2n+1|Πn|
より|Πn|の漸化式が得られました!あとは|Π1|=21とあわせて,
|Πn|=2n(n+1)2
が分かります.

おわりに

たくさん一対一対応をして計算できる形に持っていくのが面白かったです. 結果が綺麗なので, もう少し初等的な解法もあるのか気になります. ここまで読んでくれてありがとうございました!

参考文献

投稿日:2023221
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

翁
49
4265

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. 証明
  3. ①一対一対応
  4. ②経路の数え上げ
  5. おわりに
  6. 参考文献