分からない問題はここに書いてね453

**１３２人目の素数さん** · 2019/05/17(金) 06:10:41.72

さあ、今日も１日がんばろう★☆

前スレ
分からない問題はここに書いてね452
http://rio2016.5ch.net/test/read.cgi/math/1555080760/

(使用済です: 478)

**１３２人目の素数さん** · 2019/06/10(月) 20:37:06.58

2n x 2n の正方形を
1 x 2 のドミノで埋める場合の数を考えます

たとえば、2x2の正方形を1x2のドミノで埋める場合の数は、2通りです

4x4の正方形を1x2のドミノで埋める場合の数は、36通りです

一般に、n=0,1,2,3,,,,のとき、
1, 2, 36, 6728, 12988816, 258584046368,,,
となり、一般項は、

Π[j=1 to n]Π[j=1 to n]{4cos^2 πj/(2n+1)+4cos^2 πk/(2n+1)}

となるようなのですが、
どのようにその公式が導かれるのでしょうか?

**１３２人目の素数さん** · 2019/06/11(火) 01:30:57.91

>>490
一般項の式をa[n]とおいてa[n+1]との関係

**１３２人目の素数さん** · 2019/06/11(火) 01:47:18.59

>>490
wikipedia
https://en.wikipedia.org/wiki/Domino_tiling
によると
Temperley & Fisher (1961) and Kasteleyn (1961)
によって独立に発見されたとある。
多分元論文は
Temperley, H. N. V.; Fisher, Michael E. (1961), "Dimer problem in statistical mechanics-an exact result", Philosophical Magazine, 6 (68): 1061–1063, doi:10.1080/14786436108243366
と
Kasteleyn, P. W. (1961), "The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice", Physica, 27 (12): 1209–1225, Bibcode:1961Phy....27.1209K, doi:10.1016/0031-8914(61)90063-5.
だと思う。
多分原論文読むのが早いのでは？

**１３２人目の素数さん** · 2019/06/11(火) 04:25:10.86

脇道に逸れるが･･･

m×n の長方形の場合は
Π(j=1…[m/2]) Π(k=1…[n/2])　{4cos(jπ/(m+1))^2 + 4cos(kπ/(n+1))^2}
らしい。

2×n 長方形の場合は
　φ = (1+√5)/2 = 1.61803399　とおく。　　… 黄金比
　φ - 1/φ = 1,
Π(k=1…[n/2]) {1 + 4cos(kπ/(n+1))^2}
　= Π(k=1…[n/2]) {3 + 2cos(2kπ/(n+1))}
　= Π(k=1…[n/2]) {φ^2 + (-1/φ)^2 + 2cos(2kπ/(n+1))}
　= Π(k=1…[n/2]) {φ - (-1/φ)exp(2ik/(n+1))} {φ - (-1/φ)exp(-2ikπ/(n+1))}
　= Π(k=1…n) {φ - (-1/φ)exp(2ikπ/(n+1))}
　= {φ^(n+1) - (-1/φ)^(n+1)}/(φ + 1/φ)
　= F_(n+1)　　　　　　　　　　　　… フィボナッチ数

参考文献
・数セミ増刊「数学100の問題」日本評論社(1984) p.90-92
　http://oeis.org/A004003
　http://oeis.org/A065072

**１３２人目の素数さん** · 2019/06/11(火) 05:56:39.98

>>490
これに証明載ってるくさい。
https://inis.iaea.org/collection/NCLCollectionStore/_Public/38/098/38098203.pdf?r=1&;r=1

Section2
A famous result of Kasteleyn [8] and Temperley and Fisher [18] counts the
number of domino tilings of a chessboard (or any other rectangular region).
In this section we explain Kasteleyn's proof.

だそうな。

**１３２人目の素数さん** · 2019/06/11(火) 06:03:53.49

・2×2n の長方形
　特性多項式　tt-t-1,
　-1/φ = (1-√5)/2,
　φ = (1+√5)/2,
　F_(n+1) = {φ^(n+1) - (-1/φ)^(n+1)}/(φ + 1/φ),
　生成関数　1/(1-z-zz),

・3×2n の長方形
　特性多項式　tt -4t +1,
　α = 2-√3,　β = 2+√3,
　P_n = {(1+√3)β^n - (1-√3)α^n}/(β-α)
　生成関数　(1-z^3)/(1-4z^3+z^6)

「ドミノによるタイル張り」(京大･理)　36p.
http://www.ms.u-tokyo.ac.jp/~kazushi/proceedings/domino.pdf

「長方形領域のドミノタイル張りについて」(青学大･理工)　17p.
http://www.gem.aoyama.ac.jp/~kyo/sotsuken/2010/fujino_sotsuron_2010.pdf