前回の「ドミノタイリングの数え上げ（その１）」ではドミノタイリングを格子グラフに変換してさらにタイル張り問題として数える方法を紹介しました。
この考え方はタイルのパターンを変えるだけで、いくつかの他の問題にも適用できます。今回はそのコードをそのまま利用して以下のOEISの答えを求めていきます。
OEISの題名はかなり分かりづらいので、下で実際に作った例を見てもらったほうが良いかもしれません。
| OEIS# | 定義 （$L_N$は$N \times N$の格子グラフ） |
N=2の例 |
|---|---|---|
| A004003 | すべての頂点から辺が1本 $deg(v)=1 \ \ \forall v \in L_N $ |
 |
| A222202 | すべての頂点から辺が２本 $deg(v)=2 \ \ \forall v \in L_N $ |
 |
| A216678 | すべての頂点から出る辺と入る辺が各々1本 (ループ２なし) $deg^+(v)=deg^-(v)=1 \ \ \forall v \in L_N$ $(No \ 2loops)$ |
 |
| A216675 | すべての頂点から出る辺と入る辺が各々1本 (ループ２あり) $deg^+(v)=deg^-(v)=1 \ \ \forall v \in L_N $ |
 |
【A222202】 すべての頂点から辺が２本
４方向の辺から２個を選ぶので以下の６通りです。
TILES = [(1,1,0,0),(0,1,1,0),(0,0,1,1),(1,0,0,1),(1,0,1,0),(0,1,0,1)] # deg(v) = 2 for all v in Ln)
このデータだけを置き換えてその１で作ったコードを走らせると以下の結果が得られました。
| N | 組合せの数 |
|---|---|
| 2 | 1 |
| 4 | 18 |
| 6 | 13903 |
| 8 | 360783593 |
| 10 | 303872744726644 |
| 12 | 8217125138015950451626 |
| 14 | 7095967027221343377167292602835 |
| 16 | 195081705501438193439250404333039349462635 |
N=4の時の18通りは以下の様になります。
【A216678】 すべての頂点から出る辺と入る辺が各々1本 (ループ２なし)
辺に向きが加わるので上と右を2, 下と左を３で表すと以下の12通りのデータになります。
TILES = [( 0,3,0,3),(3,0,3,0),(0,2,0,2),(2,0,2,0), # deg+(v) = deg-(v) = 1 for all v in Ln)
(3,3,0,0),(0,2,3,0),(0,0,2,2),(2,0,0,3),
(2,2,0,0),(0,3,2,0),(0,0,3,3),(3,0,0,2)]
コード自体は変更する必要がなく、以下の結果が得られました。
| N | 組合せの数 |
|---|---|
| 2 | 2 |
| 4 | 88 |
| 6 | 207408 |
| 8 | 22902801416 |
| 10 | 112398351350823112 |
| 12 | 24075116871728596710774372 |
N=4の88通りのうち18個を表示します
【A216675】 すべての頂点から出る辺と入る辺が各々1本 (ループ２あり)
２頂点間のループはドミノタイリングのデータと同じですが区別するために値を４にします。ループ２なしのデータに以下の４つを加えます。
TILES += [(4,0,0,0),(0,4,0,0),(0,0,4,0),(0,0,0,4)]
| N | 組合せの数 |
|---|---|
| 2 | 4 |
| 4 | 1296 |
| 6 | 45265984 |
| 8 | 168709341081856 |
| 10 | 66865709036047973991424 |
N=4の1296通りのうち18個を表示します
（開発環境：Google Colab）
この考え方はProject Euler Problem 393: Migrating Antsを解くのに役に立ちます。