폴리오미노(polyomino)는 유한한 개수의 단위 정사각형들이 변과 변을 맞대어 연결되어 이루어진 평면 기하 도형이다. 이는 정사각형 타일링의 유한하고 연결된 부분 집합으로 간주할 수 있다.
개요
폴리오미노라는 용어는 1953년 하버드 대학교의 솔로몬 골롬(Solomon W. Golomb) 박사가 수학 강의 중 처음 사용하였으며, 이후 마틴 가드너(Martin Gardner)가 1960년 11월 Scientific American지의 "Mathematical Games" 칼럼을 통해 대중화하였다. 폴리오미노를 구성하는 정사각형의 개수에 따라 명칭이 달라지며, 접미사 -omino 앞에 그리스어 수사 어근이 붙는 방식으로 이름이 정해진다. 이 명명법은 도미노(domino)라는 단어에서 역성(back-formation)된 것이다.
분류 기준
폴리오미노는 구별 방식에 따라 세 가지로 분류된다.
- 자유(free) 폴리오미노: 평행 이동, 회전, 반사(뒤집기)를 통해 동일해지는 것은 같은 것으로 간주한다.
- 단면(one-sided) 폴리오미노: 평행 이동과 회전은 허용하나, 반사(뒤집기)는 허용하지 않아 거울상이 서로 다른 것으로 간주된다.
- 고정(fixed) 폴리오미노: 평행 이동만 허용하며, 회전이나 반사된 형태는 모두 서로 다른 것으로 간주한다. 통계 물리학에서는 이를 "격자 동물"(lattice animals)이라고도 부른다.
정사각형 개수에 따른 분류
| 이름 | n | 자유 | 단면 | 고정 |
|---|---|---|---|---|
| 모노미노(monomino) | 1 | 1 | 1 | 1 |
| 도미노(domino) | 2 | 1 | 1 | 2 |
| 트로미노(tromino) | 3 | 2 | 2 | 6 |
| 테트로미노(tetromino) | 4 | 5 | 7 | 19 |
| 펜토미노(pentomino) | 5 | 12 | 18 | 63 |
| 헥소미노(hexomino) | 6 | 35 | 60 | 216 |
| 헵토미노(heptomino) | 7 | 108 | 196 | 760 |
| 옥토미노(octomino) | 8 | 369 | 704 | 2,725 |
| 노노미노(nonomino) | 9 | 1,285 | 2,500 | 9,910 |
| 데코미노(decomino) | 10 | 4,655 | 9,189 | 36,446 |
헵토미노(7개) 이상부터는 내부에 구멍(hole)이 있는 폴리오미노가 존재한다. 헵토미노 중 1개, 옥토미노 중 6개가 구멍을 포함한다.
수학적 성질
고정 폴리오미노의 개수 t(n)은 n이 증가함에 따라 지수적으로 증가하며, 극한 λ = lim_{n→∞} (t(n))^{1/n}이 존재함이 증명되어 있다. 이 극한값 λ는 "클라르너 상수"(Klarner's constant)라고 불리며, 현재까지 알려진 가장 좋은 추정치는 약 4.0626이다. 하한은 4.00253, 상한은 4.5252로 알려져 있다.
n개의 정사각형으로 이루어진 폴리오미노의 개수를 구하는 일반 공식은 아직 발견되지 않았으며, 이는 현재까지 해결되지 않은 조합론적 문제로 남아 있다.
폴리오미노의 활용
폴리오미노는 레크리에이션 수학에서 널리 활용된다. 펜토미노(5개) 12종을 이용한 직사각형 맞추기 퍼즐이 대표적이며, 6×10, 5×12, 4×15, 3×20 크기의 직사각형을 채우는 것이 가능하다. 비디오 게임 테트리스(Tetris)는 7가지의 단면 테트로미노(게임 내에서는 "테트리미노"라고 표기)를 기반으로 한다. 보드 게임 블로커스(Blokus)는 펜토미노까지의 모든 자유 폴리오미노를 사용한다.
통계 물리학에서는 폴리오미노가 분지 고분자(branched polymer) 및 침투 클러스터(percolation cluster)의 모형으로 사용된다. 또한 가환대수학(commutative algebra)에서도 폴리오미노의 꼭짓점에 대응하는 변수들로 정의되는 이항 아이디얼(binomial ideal) 연구에 활용된다.
관련 개념
폴리오미노의 일반화로는 정삼각형을 기본 단위로 하는 폴리아몬드(polyiamond), 정육각형을 기본 단위로 하는 폴리헥스(polyhex), 3차원 공간에서 정육면체를 연결한 폴리큐브(polycube) 등이 있다.
