位数
位数
ドミノで敷き詰め
実は, 位数
①とある経路とドミノでの敷き詰めを一対一対応させる
②一対一対応させた経路の数を数え上げる
与えられたドミノでの敷き詰めを, 経路(の組)に変換することを考えます. 具体的には、次のようにします:
先ほどの敷き詰めの例を使うと, 図5のような経路を得ることが出来ます.
始点
矢印の引きかた
経路の例
さらに, アステカダイヤモンドを図6のように市松模様で塗り分けると, 経路上の点は全て色付きのマスの左側の辺(
市松模様
加えて, これらの経路は決して交差しないことが分かります. (ふたつの経路が交差するとは, 経路が同じ点を共有することをいいます. 交差すると仮定すると, 図7の示すいずれかの状況になる必要がありますが, それはどれも不可能です. )
このようにはならない
逆に, アステカダイヤモンドに対して
・始点を図3のように定め
・
・経路同士が交差しないように
経路を書き込むと, その経路から一意にドミノの敷き詰めを定めることができます.
まず, 経路は交差しないので, 書き込んだ経路が通るマスにはドミノを一意に敷き詰めることができます. したがって, 経路が書き込まれていないマスにドミノを一意に敷き詰められることが言えればいいわけです. ここで, 経路が色付きのマスを通ることと経路がその一つ左の白いマスを通ることが(始点・終点以外の位置で)同値であることより, 経路が書き込まれていないマスは, 左が白いマスで右が色付きのマスである横倒しのドミノで敷き詰められることが分かります. これ以外のドミノを少なくともひとつ使って経路が通らないマスを敷き詰められたと仮定すると, そのドミノから図4のルールに従って左右に経路を伸ばしていけば, 結局このドミノはいずれかの経路に組み込まれてしまうことになり, 矛盾します.以上より経路からドミノの敷き詰めが一意に決まることが示されました.
以上より, 条件をみたす非交差経路の組の数を数える問題に帰着することができました!
非交差経路
図8のように, 最下段のマスを通るように
(i)
(ii)
の条件を満たす経路を
さらに, (i)と(ii)に加えて
(iii)
の条件を満たして
ここでいくつかの補題を用意します:
図8における直線
を
を
LGV公式より従う. LGV公式については こちら を参照.
(iii)をみたさない経路について, 左から見たときに最後に登場する
経路
経路
図では
以上より
補題2と補題3より,
が従うので, 補題1とあわせて
より
が分かります.
たくさん一対一対応をして計算できる形に持っていくのが面白かったです. 結果が綺麗なので, もう少し初等的な解法もあるのか気になります. ここまで読んでくれてありがとうございました!