前回のその３では畳タイリングのパターンを実際にパターンを求める方法をコーティングしました。今回はその場合の数だけをより高速に求めることを考えます。
畳タイリングの場合の数を求める母関数
英語版のDomino tiling#Tatami (Wikipedia)には畳タイリングの項目があり、以下の論文が参照されています
Ruskey, Frank; Woodcock, Jennifer (2009), "Counting fixed-height Tatami tilings"
この論文では畳タイリングの場合の数は以下の母関数（Generating Function）で表せると言っています。
\begin{equation}
T_m(z)=\sum_{n \ge 0}T(m,n)z^n
=
\begin{cases}
1 & \text{for m} = 0\\
\large \frac{1}{1-z^2} &\text{for m} = 1\\
\large \frac{1+x^2}{1-z-z^3} &\text{for m} = 2\\
\large \frac{1+z^{m-1}+z^{m+1}}{1-z^{m-1}-z^{m+1}} & \text{for m odd, } 3 \le m \le n \\
\large \frac{(1+z)(1+z^{m-2}+z^m)}{1-z^{m-1}-z^{m+1}} &\text{for m even, } 4\le m \le n
\end{cases}
\end{equation}
母関数に馴染みのない方はなんのこっちゃと思うかもしれません。母関数に興味のある方はぜひ「やさしい母関数（Generating Function）（その１）」から「（その７）」までの投稿を参照して下さい。
わからなくても良いからコードをとりあえず書きたいのであれば、「やさしい母関数（Generating Function）（その３」の最後に添付した関数gf2listを使えば母関数から数列に変換してくれます。
gf2listを使って畳タイリングの場合の数を返す関数tatamiは上の母関数そのままコードにすればOKです。
def tatami(m, n):
def tgf(m, n):
if m == 1: return 1 / (1-x**2)
if m == 2: return (1+x**2) / (1-x-x**3)
if m % 2 == 1: return (1+x**(m-1)+x**(m+1)) / (1-x**(m-1)-x**(m+1)) # m: odd
return (1+x)*(1+x**(m-2)+x**m) / (1-x**(m-1)-x**(m+1)) # m: even
if m == 0: return ([0] * n)
return gf2list(tgf(m,n), n)
for n, m in [(4,4), (6,6), (8, 8), (7,10) ]:
print(f"# (n, m) = {(n, m)}: Tatami tiling = {tatami(m,n)[n]}")
# (n, m) = (4, 4): Tatami tiling = 2
# (n, m) = (6, 6): Tatami tiling = 2
# (n, m) = (8, 8): Tatami tiling = 2
# (n, m) = (7, 10): Tatami tiling = 0
となり、前回と同じ答えを得ることが出来ました。
畳タイリングが可能かどうかだけを調べる
前回に16x16までの畳タイリングの場合の数を求めましたが、何かパターンがありそうでした。今回は畳タイリングが出来るか(場合の数＞０)に注目して$256 \times 256$まで求め、そのパターンをビットマップにしてみました。
import numpy as np
import matplotlib.pyplot as plt
M, N = 256, 256
T = []
for m in range(M+1):
tl = tatami(m, N)
T.append([-1 if i < m else 1 if tl[i]>0 else 0 for i in range(N+1)])
#--- mirroring case m > n
for m in range(M+1):
for n in range(m):
T[m][n] = T[n][m]
T = np.array(T)
T = T.astype(float)
im = plt.imshow(T)
- 黄： 場合の数 ＞ ０
- 緑： 場合の数 = ０
この図を見て気付くのは黄色の点は$y=ax\ (aは自然数)$の上にある幅を持って存在しているます。詳細に見てみるとｘ方向の幅は$\pm (a+1)$であることが分かりました。従って、畳タイリングの場合の数を０か０以上かを求めるのであれば、母関数を使ったtatamiの代わりに以下のtatami1を使うことが出来ます。
def tatami1(m, n):
if m == 0: return 0
if n < m: return -1
if m * n % 2 == 1: return 0 # odd x odd
d, r = divmod(n, m)
return int((m-d-2) <= r or r <= d+1) # True / False -> 1 / 0
（開発環境：Google Colab）
この考え方はProject Euler Problem 256: Tatami-Free Roomsを解くのに役に立ちます。