200414

PARI


Number of domino tilings of the n X k grid

n X k の長方形をk*n/2 個のドミノで埋め尽くす方法が何通りあるかという問題に対し、
Temperley & Fisher とKasteleyn によってそれぞれ独立に得られた公式がよく知られている。

この公式を言い換えて、より簡単に計算する方法に気がついた。

求めるものをT(n,k) とすると、

T(n,k)^2 = |Res(U_n(x/2), U_k(i*x/2))|

（ただし、U_n(x) は第二種チェビシェフ多項式）

と表される。

これを用いて、T(n,k) を計算してみた。

(11:13) gp > T(n, k) = sqrtint(abs(polresultant(polchebyshev(n, 2, x/2), polchebyshev(k, 2, I*x/2))));
(11:14) gp > for(n=0, 15, for(k=0, 10, print1(T(n, k), ", ")); print)
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
1, 0, 3, 0, 11, 0, 41, 0, 153, 0, 571,
1, 1, 5, 11, 36, 95, 281, 781, 2245, 6336, 18061,
1, 0, 8, 0, 95, 0, 1183, 0, 14824, 0, 185921,
1, 1, 13, 41, 281, 1183, 6728, 31529, 167089, 817991, 4213133,
1, 0, 21, 0, 781, 0, 31529, 0, 1292697, 0, 53175517,
1, 1, 34, 153, 2245, 14824, 167089, 1292697, 12988816, 108435745, 1031151241,
1, 0, 55, 0, 6336, 0, 817991, 0, 108435745, 0, 14479521761,
1, 1, 89, 571, 18061, 185921, 4213133, 53175517, 1031151241, 14479521761, 258584046368,
1, 0, 144, 0, 51205, 0, 21001799, 0, 8940739824, 0, 3852472573499,
1, 1, 233, 2131, 145601, 2332097, 106912793, 2188978117, 82741005829, 1937528668711, 65743732590821,
1, 0, 377, 0, 413351, 0, 536948224, 0, 731164253833, 0, 1012747193318519,
1, 1, 610, 7953, 1174500, 29253160, 2720246633, 90124167441, 6675498237130, 259423766712000, 16848161392724969,
1, 0, 987, 0, 3335651, 0, 13704300553, 0, 59554200469113, 0, 264499788583572499,
(11:14) gp >