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

2021년 2월 17일 (수) 04:46 기준 최신판

개요

사각격자를 도미노로 덮는 문제
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.

메타데이터

위키데이터

ID : Q21042776

Spacy 패턴 목록

[{'LOWER': 'domino'}, {'LEMMA': 'tiling'}]

@@ 1번째 줄: / 1번째 줄: @@
-==이 항목의 수학노트 원문주소==
 ==개요==
@@ 12번째 줄: / 6번째 줄: @@
 * 통계물리에서는 dimer configuration = covering of a graph by pairs of fermions connected by an edge
-==2x2 격자==
-*  다음 두 가지 경우가 존재<br>[[파일:10224838-dimer1.gif]]<br>
-*  다음 행렬의 [[파피안(Pfaffian)]] 을 구해서 경우의 수를 얻을 수 있다<br><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>
-<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> 으로 주어진다. 파피안의 각 항은 도미노 타일링에 대응된다.
-==3x2 격자==
-*  다음 세 가지 경우가 존재<br>  [[파일:10224838-dimer2.gif]]<br>
-*  다음 행렬의 파피안은 3이다<br><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>
-<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> 이다.
+==예==
+===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> 으로 주어진다.
+* 파피안의 각 항은 도미노 타일링에 대응된다.
-==역사==
+===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> 이다.
-* http://www.google.com/search?hl=en&tbs=tl:1&q=
+===4x4 격자===
-* [[수학사연표 (역사)|수학사연표]]
+* 36개의 타일링
+[[파일:사각격자의 도미노 타일링 (dimer problem)3.png]]
+==테이블==
+* <math>m\times n</math> 격자의 도미노 타일링
+\begin{array}{c|cccccccc}
+ m \ddots n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
+\hline
+& 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
+& 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 \\
+& 0 & 3 & 0 & 11 & 0 & 41 & 0 & 153 \\
+& 1 & 5 & 11 & 36 & 95 & 281 & 781 & 2245 \\
+& 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 \\
+\end{array}
 ==메모==
-* 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=
 ==관련된 항목들==
@@ 70번째 줄: / 53번째 줄: @@
 * [[파피안(Pfaffian)]]
 ==수학용어번역==
-*  단어사전<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 대한수학회 수학용어한글화 게시판]
+==사전 형태의 자료==
-==사전 형태의 자료==
 * 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.
-[[분류:통계물리]]
+==관련논문==
+* Allegra, Nicolas. “<math>2d</math> Dimer Model, Correlation Functions and Combinatorics.” arXiv:1410.4131 [cond-Mat, Physics:math-Ph], October 15, 2014. http://arxiv.org/abs/1410.4131.
+* Florescu, Laura, Daniela Morar, David Perkinson, Nick Salter, and Tianyuan Xu. “Sandpiles and Dominos.” arXiv:1406.0100 [math], May 31, 2014. http://arxiv.org/abs/1406.0100.
+[[분류:통계물리]]
+[[분류:조합수학]]
+==메타데이터==
+===위키데이터===
+* ID :  [https://www.wikidata.org/wiki/Q21042776 Q21042776]
+===Spacy 패턴 목록===
+* [{'LOWER': 'domino'}, {'LEMMA': 'tiling'}]