"사각격자의 도미노 타일링 (dimer problem)"의 두 판 사이의 차이

2014년 5월 12일 (월) 17:51 판

개요

사각격자를 도미노로 덮는 문제
planar bipartite graph 의 perfect matching 문제로 생각할 수 있다
그래프의 적당한 weighted adjacency matrix 와 그 파피안(Pfaffian) 을 통해 답을 표현할 수 있다
통계물리에서는 dimer configuration = covering of a graph by pairs of fermions connected by an edge

예

2x2 격자

다음 두 가지 경우가 존재

다음 행렬의 파피안(Pfaffian) 을 구해서 경우의 수를 얻을 수 있다\[\left( \begin{array}{cccc} 0 & 1 & 1 & 0 \\ -1 & 0 & 0 & -1 \\ -1 & 0 & 0 & 1 \\ 0 & 1 & -1 & 0 \end{array} \right)\]
행렬 $\left( \begin{array}{cccc} 0 & t_{1,2} & t_{1,3} & 0 \\ -t_{1,2} & 0 & 0 & -t_{2,4} \\ -t_{1,3} & 0 & 0 & t_{3,4} \\ 0 & t_{2,4} & -t_{3,4} & 0 \end{array} \right)$

의 파피안은 $t_{1,3} t_{2,4}+t_{1,2} t_{3,4}$ 으로 주어진다.

파피안의 각 항은 도미노 타일링에 대응된다.

3x2 격자

다음 세 가지 경우가 존재

다음 행렬의 파피안은 3이다\[\left( \begin{array}{cccccc} 0 & 1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & -1 & 0 & 0 \\ -1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & -1 & 0 & 0 & -1 \\ 0 & 0 & -1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & -1 & 0 \end{array} \right)\]
행렬 $\left( \begin{array}{cccccc} 0 & t_{1,2} & t_{1,3} & 0 & 0 & 0 \\ -t_{1,2} & 0 & 0 & -t_{2,4} & 0 & 0 \\ -t_{1,3} & 0 & 0 & t_{3,4} & t_{3,5} & 0 \\ 0 & t_{2,4} & -t_{3,4} & 0 & 0 & -t_{4,6} \\ 0 & 0 & -t_{3,5} & 0 & 0 & t_{5,6} \\ 0 & 0 & 0 & t_{4,6} & -t_{5,6} & 0 \end{array} \right)$ 의 파피안은 $t_{1,2} t_{3,5} t_{4,6}+t_{1,3} t_{2,4} t_{5,6}+t_{1,2} t_{3,4} t_{5,6}$ 이다.

4x4 격자

36개의 타일링

테이블

$m\times n$ 격자의 도미노 타일링

\begin{array}{c|cccccccc} m \ddots n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 2 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 \\ 3 & 0 & 3 & 0 & 11 & 0 & 41 & 0 & 153 \\ 4 & 1 & 5 & 11 & 36 & 95 & 281 & 781 & 2245 \\ 5 & 0 & 8 & 0 & 95 & 0 & 1183 & 0 & 14824 \\ 6 & 1 & 13 & 41 & 281 & 1183 & 6728 & 31529 & 167089 \\ 7 & 0 & 21 & 0 & 781 & 0 & 31529 & 0 & 1292697 \\ 8 & 1 & 34 & 153 & 2245 & 14824 & 167089 & 1292697 & 12988816 \\ \end{array}

역사

메모

수학용어번역

사전 형태의 자료

리뷰논문, 에세이, 강의노트

Borcherds Lecture 26 Pfaffians and dominoes
Propp, James. “Dimers and Dominoes.” arXiv:1405.2615 [math], May 11, 2014. http://arxiv.org/abs/1405.2615.

@@ 1번째 줄: / 1번째 줄: @@
-==이 항목의 수학노트 원문주소==
 ==개요==
@@ 12번째 줄: / 6번째 줄: @@
 * 통계물리에서는 dimer configuration = covering of a graph by pairs of fermions connected by an edge
+==예==
+===2x2 격자===
+*  다음 두 가지 경우가 존재
+[[파일:사각격자의 도미노 타일링 (dimer problem)1.png]]
+*  다음 행렬의 [[파피안(Pfaffian)]] 을 구해서 경우의 수를 얻을 수 있다:<math>\left( \begin{array}{cccc}  0 & 1 & 1 & 0 \\  -1 & 0 & 0 & -1 \\  -1 & 0 & 0 & 1 \\  0 & 1 & -1 & 0 \end{array} \right)</math>
+* 행렬 <math>\left( \begin{array}{cccc}  0 & t_{1,2} & t_{1,3} & 0 \\  -t_{1,2} & 0 & 0 & -t_{2,4} \\  -t_{1,3} & 0 & 0 & t_{3,4} \\  0 & t_{2,4} & -t_{3,4} & 0 \end{array} \right)</math>
+의 파피안은 <math>t_{1,3} t_{2,4}+t_{1,2} t_{3,4}</math> 으로 주어진다.
+* 파피안의 각 항은 도미노 타일링에 대응된다.
-==2x2 격자==
+===3x2 격자===
+*  다음 세 가지 경우가 존재
+[[파일:사각격자의 도미노 타일링 (dimer problem)2.png]]
+*  다음 행렬의 파피안은 3이다:<math>\left( \begin{array}{cccccc}  0 & 1 & 1 & 0 & 0 & 0 \\  -1 & 0 & 0 & -1 & 0 & 0 \\  -1 & 0 & 0 & 1 & 1 & 0 \\  0 & 1 & -1 & 0 & 0 & -1 \\  0 & 0 & -1 & 0 & 0 & 1 \\  0 & 0 & 0 & 1 & -1 & 0 \end{array} \right)</math>
+* 행렬 <math>\left( \begin{array}{cccccc}  0 & t_{1,2} & t_{1,3} & 0 & 0 & 0 \\  -t_{1,2} & 0 & 0 & -t_{2,4} & 0 & 0 \\  -t_{1,3} & 0 & 0 & t_{3,4} & t_{3,5} & 0 \\  0 & t_{2,4} & -t_{3,4} & 0 & 0 & -t_{4,6} \\  0 & 0 & -t_{3,5} & 0 & 0 & t_{5,6} \\  0 & 0 & 0 & t_{4,6} & -t_{5,6} & 0 \end{array} \right)</math> 의 파피안은 <math>t_{1,2} t_{3,5} t_{4,6}+t_{1,3} t_{2,4} t_{5,6}+t_{1,2} t_{3,4} t_{5,6}</math> 이다.
-*  다음 두 가지 경우가 존재<br>[[파일:10224838-dimer1.gif]]<br>
-*  다음 행렬의 [[파피안(Pfaffian)]] 을 구해서 경우의 수를 얻을 수 있다:<math>\left( \begin{array}{cccc}  0 & 1 & 1 & 0 \\  -1 & 0 & 0 & -1 \\  -1 & 0 & 0 & 1 \\  0 & 1 & -1 & 0 \end{array} \right)</math><br>
+===4x4 격자===
+* 36개의 타일링
+[[파일:사각격자의 도미노 타일링 (dimer problem)3.png]]
-<math>\left( \begin{array}{cccc}  0 & t_{1,2} & t_{1,3} & 0 \\  -t_{1,2} & 0 & 0 & -t_{2,4} \\  -t_{1,3} & 0 & 0 & t_{3,4} \\  0 & t_{2,4} & -t_{3,4} & 0 \end{array} \right)</math> 의 파피안은 <math>t_{1,3} t_{2,4}+t_{1,2} t_{3,4}</math> 으로 주어진다. 파피안의 각 항은 도미노 타일링에 대응된다.
+==테이블==
+* $m\times n$ 격자의 도미노 타일링
+\begin{array}{c|cccccccc}
+  m \ddots n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
+\hline
+& 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
-==3x2 격자==
+& 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 \\
+& 0 & 3 & 0 & 11 & 0 & 41 & 0 & 153 \\
-*  다음 세 가지 경우가 존재<br>  [[파일:10224838-dimer2.gif]]<br>
+& 1 & 5 & 11 & 36 & 95 & 281 & 781 & 2245 \\
-*  다음 행렬의 파피안은 3이다:<math>\left( \begin{array}{cccccc}  0 & 1 & 1 & 0 & 0 & 0 \\  -1 & 0 & 0 & -1 & 0 & 0 \\  -1 & 0 & 0 & 1 & 1 & 0 \\  0 & 1 & -1 & 0 & 0 & -1 \\  0 & 0 & -1 & 0 & 0 & 1 \\  0 & 0 & 0 & 1 & -1 & 0 \end{array} \right)</math><br>
+& 0 & 8 & 0 & 95 & 0 & 1183 & 0 & 14824 \\
+& 1 & 13 & 41 & 281 & 1183 & 6728 & 31529 & 167089 \\
+& 0 & 21 & 0 & 781 & 0 & 31529 & 0 & 1292697 \\
+& 1 & 34 & 153 & 2245 & 14824 & 167089 & 1292697 & 12988816 \\
-<math>\left( \begin{array}{cccccc}  0 & t_{1,2} & t_{1,3} & 0 & 0 & 0 \\  -t_{1,2} & 0 & 0 & -t_{2,4} & 0 & 0 \\  -t_{1,3} & 0 & 0 & t_{3,4} & t_{3,5} & 0 \\  0 & t_{2,4} & -t_{3,4} & 0 & 0 & -t_{4,6} \\  0 & 0 & -t_{3,5} & 0 & 0 & t_{5,6} \\  0 & 0 & 0 & t_{4,6} & -t_{5,6} & 0 \end{array} \right)</math> 의 파피안은 <math>t_{1,2} t_{3,5} t_{4,6}+t_{1,3} t_{2,4} t_{5,6}+t_{1,2} t_{3,4} t_{5,6}</math> 이다.
+\end{array}
 ==역사==
@@ 54번째 줄: / 55번째 줄: @@
 ==메모==
-* 8x8 격자에는 12988816 경우의 도미노 타일링이 있다
 * http://www.science.uva.nl/onderwijs/thesis/centraal/files/f887198315.pdf
 * [http://www.math.oregonstate.edu/%7Emath_reu/REU_Proceedings/Proceedings1991/Klarreich91.pdf http://www.math.oregonstate.edu/~math_reu/REU_Proceedings/Proceedings1991/Klarreich91.pdf]
-* Borcherds [http://math.berkeley.edu/%7Ereb/courses/261/26.pdf Lecture 26 Pfaffians and dominoes]
-* Math Overflow http://mathoverflow.net/search?q=
 ==관련된 항목들==
@@ 76번째 줄: / 70번째 줄: @@
 ==수학용어번역==
-*  단어사전<br>
-** http://translate.google.com/#en|ko|
-** http://ko.wiktionary.org/wiki/
-* 발음사전 http://www.forvo.com/search/
-* [http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=&fstr= 대한수학회 수학 학술 용어집]<br>
-** http://mathnet.kaist.ac.kr/mathnet/math_list.php?mode=list&ftype=eng_term&fstr=
-* [http://www.kss.or.kr/pds/sec/dic.aspx 한국통계학회 통계학 용어 온라인 대조표]
-* [http://www.nktech.net/science/term/term_l.jsp?l_mode=cate&s_code_cd=MA 남·북한수학용어비교]
-* [http://kms.or.kr/home/kor/board/bulletin_list_subject.asp?bulletinid=%7BD6048897-56F9-43D7-8BB6-50B362D1243A%7D&boardname=%BC%F6%C7%D0%BF%EB%BE%EE%C5%E4%B7%D0%B9%E6&globalmenu=7&localmenu=4 대한수학회 수학용어한글화 게시판]
@@ 96번째 줄: / 77번째 줄: @@
 * http://ko.wikipedia.org/wiki/
 * http://en.wikipedia.org/wiki/Domino_tiling
-* [http://eom.springer.de/default.htm The Online Encyclopaedia of Mathematics]
-* [http://dlmf.nist.gov/ NIST Digital Library of Mathematical Functions]
-* [http://eqworld.ipmnet.ru/ The World of Mathematical Equations]
 ==리뷰논문, 에세이, 강의노트==
+* Borcherds [http://math.berkeley.edu/%7Ereb/courses/261/26.pdf Lecture 26 Pfaffians and dominoes]
+* Propp, James. “Dimers and Dominoes.” arXiv:1405.2615 [math], May 11, 2014. http://arxiv.org/abs/1405.2615.
 [[분류:통계물리]]
+[[분류:조합수학]]