폴리오미노

3. 폴리오미노의 개수

n이 커짐에 따라 폴리오미노의 개수는 지수적으로 증가한다. 다음 표는 다양한 유형의 폴리오미노에서 n개의 셀 수를 보여준다.

고정 폴리오미노는 Iwan Jensen에 의해 ''n'' = 56까지, Gill Barequet와 Gil Ben-Shachar에 의해 ''n'' = 70까지 열거되었다.^[9]

자유 폴리오미노는 Tomás Oliveira e Silva에 의해 ''n'' = 28까지,^[10] Toshihiro Shirakawa에 의해 ''n'' = 45까지,^[11] John Mason에 의해 ''n'' = 50까지 열거되었다.^[12]

폴리오미노를 열거할 때 구별하는 세 가지 일반적인 방법은 다음과 같다.^[6][7]

• ''자유'' 폴리오미노는 다른 폴리오미노를 평행이동, 회전, 반사 또는 글라이드 반사로 변환할 수 없을 때 서로 다르다고 간주한다(집어 올리고 뒤집을 수 있는 조각).
• ''일면'' 폴리오미노는 다른 폴리오미노를 평행이동 또는 회전으로 변환할 수 없을 때 서로 다르다고 간주한다(뒤집을 수 없는 조각).
• ''고정'' 폴리오미노는 다른 폴리오미노를 평행이동으로 변환할 수 없을 때 서로 다르다고 간주한다(뒤집거나 회전할 수 없는 조각).

4. 대칭성

폴리오미노는 다양한 대칭성을 가질 수 있으며, 이는 폴리오미노의 개수를 계산하는 데 영향을 미친다. 정사각형의 대칭군인 이면체군 D₄는 네 개의 회전과 네 개의 반사를 포함한다. 폴리오미노의 가능한 대칭은 다음과 같다:^[13]

• 대칭 없음 (4): 각 자유 폴리오미노에 대해 8개의 고정 폴리오미노가 존재한다.
• 격자선 방향 중 하나에 대한 거울 대칭 (4): 각 자유 폴리오미노에 대해 4개의 고정 폴리오미노가 존재한다.
• 대각선에 대한 거울 대칭 (3): 각 자유 폴리오미노에 대해 4개의 고정 폴리오미노가 존재한다.
• 2겹 회전 대칭: ''C''₂ (4): 각 자유 폴리오미노에 대해 4개의 고정 폴리오미노가 존재한다.
• 두 격자선 방향 모두에 대한 대칭, 따라서 2겹 회전 대칭: ''D''₂ (2) (클라인 사원군으로도 알려짐): 각 자유 폴리오미노에 대해 2개의 고정 폴리오미노가 존재한다.
• 두 대각선 방향 모두에 대한 대칭, 따라서 2겹 회전 대칭: ''D''₂ (7): 각 자유 폴리오미노에 대해 2개의 고정 폴리오미노가 존재한다.
• 4겹 회전 대칭: ''C''₄ (8): 각 자유 폴리오미노에 대해 2개의 고정 폴리오미노가 존재한다.
• 정사각형의 모든 대칭: ''D''₄ (1): 각 자유 폴리오미노에 대해 1개의 고정 폴리오미노가 존재한다.

5. 폴리오미노의 열거 알고리즘

크기가 ''n''+1인 각 폴리오미노는 크기가 ''n''인 폴리오미노에 정사각형을 추가하여 얻을 수 있다. 이는 폴리오미노를 귀납적으로 생성하는 알고리즘으로 이어진다.^[15]

가장 간단한 방법은, 크기가 ''n''인 폴리오미노 목록이 주어졌을 때, 각 폴리오미노 옆에 가능한 모든 위치에 정사각형을 추가하고, 이미 발견된 것과 중복되지 않는 경우 크기가 ''n''+1인 결과 폴리오미노를 목록에 추가하는 것이다. 열거 순서를 개선하고 고려하지 않아야 할 인접한 정사각형을 표시하면 중복을 확인할 필요가 있는 경우의 수를 줄일 수 있다.^[15] 이 방법은 자유 폴리오미노 또는 고정 폴리오미노를 열거하는 데 사용할 수 있다.

Redelmeier가 설명한 보다 정교한 방법은 많은 저자가 폴리오미노를 계산할 뿐만 아니라 (크기가 ''n''+1인 폴리오미노를 열거하기 위해 크기가 ''n''인 모든 폴리오미노를 저장할 필요 없이) 그 수에 대한 상한을 증명하는 방법으로 사용해 왔다. 기본 아이디어는 단일 정사각형으로 시작하여 거기에서 재귀적으로 정사각형을 추가하는 것이다. 세부 사항에 따라 각 ''n''-오미노를 ''n''번 계산할 수 있으며, 각 정사각형에서 시작하여 한 번 계산하거나, 한 번만 계산하도록 배열할 수 있다.

가장 간단한 구현은 한 번에 하나의 정사각형을 추가하는 것이다. 초기 정사각형으로 시작하여 인접한 정사각형에 위쪽부터 시계 방향으로 1, 2, 3, 4의 번호를 매긴다. 이제 1에서 4 사이의 숫자를 선택하고 해당 위치에 정사각형을 추가한다. 번호가 매겨지지 않은 인접한 정사각형에 5부터 번호를 매긴다. 그런 다음 이전에 선택한 숫자보다 큰 숫자를 선택하고 해당 정사각형을 추가한다. 현재 정사각형의 숫자보다 큰 숫자를 선택하고 해당 정사각형을 추가한 다음 새로운 인접한 정사각형에 번호를 매기는 것을 계속한다. ''n''개의 정사각형이 생성되면 ''n''-오미노가 생성된다.

이 방법은 각 고정 폴리오미노가 각 시작 정사각형에 대해 정확히 ''n''번 계산되도록 한다. 각 폴리오미노를 ''n''번이 아닌 한 번만 계산하도록 최적화할 수 있다. 초기 정사각형으로 시작하여 폴리오미노의 왼쪽 아래 정사각형으로 선언한다. 동일한 행의 정사각형보다 아래쪽 행에 있거나 왼쪽에 있는 정사각형에는 번호를 매기지 않는다. 이것이 Redelmeier가 설명한 버전이다.

자유 폴리오미노를 대신 계산하려는 경우 각 ''n''-오미노를 생성한 후 대칭성을 확인할 수 있다. 그러나 대칭 폴리오미노를 (이 방법의 변형으로) 별도로 생성하는 것이 더 빠르므로^[16] 번사이드 보조정리를 사용하여 자유 폴리오미노의 수를 결정할 수 있다.^[17]

고정 폴리오미노를 열거하는 가장 현대적인 알고리즘은 이반 옌센에 의해 발견되었다.^[18] 앤드루 콘웨이의 방법론을 개선한 것으로,^[19] 이전 방법보다 지수적으로 빠르다(하지만, 실행 시간은 여전히 ''n''에 대해 지수적이다).

콘웨이와 옌센의 전송 행렬 방법은 모두 특정 너비를 가진 폴리오미노의 수를 세는 것을 포함한다. 모든 너비에 대한 수를 계산하면 폴리오미노의 총 개수가 나온다. 이 방법의 기본 아이디어는 가능한 시작 행을 고려한 다음 주어진 너비의 폴리오미노를 완성하는 데 필요한 최소 사각형 수를 결정하는 것이다. 생성 함수를 사용하면 이 기술은 한 번에 많은 폴리오미노를 계산할 수 있으므로 모든 폴리오미노를 생성해야 하는 방법보다 훨씬 빠르게 실행할 수 있다.

실행 시간은 매우 뛰어나지만, 이 알고리즘은 지수적인 양의 메모리를 사용해야 한다는 단점이 있다(50보다 큰 ''n''의 경우 많은 기가바이트의 메모리가 필요하다). 다른 방법보다 프로그래밍하기 훨씬 더 어렵고, 현재 자유 폴리오미노를 계산하는 데 사용할 수 없다.

6. 폴리오미노를 사용한 타일링

폴리오미노를 사용한 타일링 문제는 레크리에이션 수학에서 자주 다루어지는 주제이다.^[29] 이러한 문제들은 크게 두 가지 유형으로 나눌 수 있다.

첫 번째 유형은 주어진 폴리오미노 집합으로 특정 영역을 채우는 문제이다. 예를 들어, 12개의 펜토미노로 6x10 직사각형을 채우는 문제가 있으며, 1960년에 2339개의 해답이 발견되었다.^[30] 이와 같이 집합 내 폴리오미노의 여러 복사본이 허용되는 경우, 주어진 집합이 채울 수 있는 다양한 영역(직사각형, 스트립, 전체 평면 등)의 계층 구조가 정의된다. 주어진 집합의 폴리오미노가 평면을 채울 수 있는지 여부는 왕 타일 집합을 폴리오미노 집합에 매핑하여 결정 불가능하다는 것이 증명되었다.^[31]

두 번째 유형은 단일 폴리오미노의 복사본으로 직사각형 또는 평면을 채우는 문제이다.^[34] 이 문제는 특정 폴리오미노에 대해 광범위하게 연구되었으며,^[35] 개별 폴리오미노에 대한 결과 표가 제공된다.^[36] 클라너와 괴벨은 모든 폴리오미노에 대해 채울 수 있는 유한한 집합의 '소수' 직사각형이 존재하며, 다른 모든 직사각형은 해당 소수 직사각형으로 채울 수 있음을 보였다.^[37][38]

단일 폴리오미노 복사본으로 평면을 타일링하는 문제도 많이 논의되었다. 1965년에 헥소미노까지의 모든 폴리오미노^[43]와 헵토미노 중 4개를 제외한 모든 폴리오미노가 평면을 타일링한다는 사실이 밝혀졌다.^[44] 이후 연구를 통해 더 큰 크기의 폴리오미노에 대한 타일링 가능성이 밝혀졌다.^[45][46][47] 평면을 타일링하는 폴리오미노는 타일링의 대칭성과 타일이 나타나는 측면(방향)의 수에 따라 분류되었다.^[48][49]

어떤 폴리오미노가 평면을 타일링할 수 있는지를 연구하는 데는 컨웨이 기준이 활용되기도 한다.^[50]

7. 폴리오미노를 활용한 퍼즐 및 게임

테트리스는 7개의 단면 테트로미노("테트리미노"라고도 함)를 사용한 비디오 게임이다.^[63] Tetris^영어는 한국에서도 큰 인기를 얻고 있다. 블로커스는 펜토미노까지의 모든 자유 폴리오미노를 사용하는 보드 게임이다. 일부 스도쿠 변형은 노노미노 모양의 영역을 사용한다.

• 단위 정방형을 장방형이나 평행사변형 등으로 변형하고, 회전에 제한을 둔다.
• 도형을 단위 정방형으로 바둑판 무늬로 색칠하고, 전체가 바둑판 무늬가 되도록 채운다.
• 상자의 형태를 고정하지 않고, 합동 도형을 여러 개 만들거나, 대칭형으로 하는 등 조건을 만족하는 형태로 배치한다.
• 동일한 형태의 폴리오미노로 장방형을 만든다.^[63]

8. 한국의 폴리오미노 문화

폴리오미노 애호가들을 영어로는 ominist^영어라고 부른다. 아시가하라 노부유키는 이것을 "미노벌레"라고 번역했다.^[59]

9. 기타

폴리오미노의 정사각형 대신, 몇 가지 다른 도형을 사용한 다각형에는 이름이 붙어 있다. 이것들을 통칭하여 폴리폼이라고 부르기도 한다.

• 정삼각형 → '''폴리아이아몬드'''
• 정육각형 → '''폴리헥스'''
• 직각 이등변삼각형 → '''폴리아볼로'''
• 정육면체 → '''폴리큐브'''

참조

_[1] 문서 "the observation that there are twelve distinctive patterns (the pentominoes) that can be formed by five connected stones on a Go board ... is attributed to an ancient master of that game" Golomb
_[2] 서적 Polyominoes Princeton University Press
_[3] 논문 More about the shapes that can be made with complex dominoes (Mathematical Games) 1960-11
_[4] 서적 Disorder in Physical Systems Oxford University Press
_[5] 서적 Tilings and Patterns https://archive.org/[...] W.H. Freeman and Company
_[6] 논문 Counting polyominoes: yet another attack
_[7] 문서 Golomb
_[8] 웹사이트 Series for lattice animals or polyominoes http://www.ms.unimel[...] 2007-05-06
_[9] 서적 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) - Counting Polyominoes, Revisited Society for Industrial and Applied Mathematics 2024-01
_[10] 웹사이트 Animal enumerations on the {4,4} Euclidean tiling http://www.ieeta.pt/[...] 2007-05-06
_[11] 웹사이트 Harmonic Magic Square, Enumeration of Polyominoes considering the symmetry https://www.gatherin[...]
_[12] 웹사이트 Counting size 50 polyominoes https://oeis.org/A00[...]
_[13] 문서 Redelmeier
_[14] 논문 Counting polyominoes: Yet another attack
_[15] 문서 Golomb
_[16] 문서 Redelmeier
_[17] 문서 Redelmeier
_[18] 논문 Enumerations of Lattice Animals and Trees 2001-02
_[19] 논문 Enumerating 2D percolation series by the finite-lattice method: theory
_[20] 논문 Statistics of lattice animals (polyominoes) and polygons
_[21] 논문 λ > 4: An Improved Lower Bound on the Growth Constant of Polyominoes
_[22] 논문 A procedure for improving the upper bound for the number of ''n''-ominoes http://historical.nc[...] 2007-05-11
_[23] 논문 " Improved upper bounds on the growth constants of polyominoes and polycubes"
_[24] 서적 Generatingfunctionology Academic Press
_[25] 논문 New enumerative results on two-dimensional directed animals
_[26] 논문 Generating functions for column-convex polyominoes
_[27] 논문 The generating function of convex polyominoes: The resolution of a ''q''-differential system
_[28] 간행물 Geometry Labs https://books.google[...] MathEducationPage.org
_[29] 서적 Polyominoes: A guide to puzzles and problems in tiling https://archive.org/[...] Mathematical Association of America
_[30] 논문 A Computer Program for Pentominoes https://www.archim.o[...] 1960-10
_[31] 논문 Tiling with Sets of Polyominoes
_[32] 논문 Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity https://link.springe[...] 2007-06
_[33] 논문 Backtrack Programming
_[34] 문서 Polyominoes Golomb
_[35] 웹사이트 References for Rectifiable Polyominoes http://www.math.ucf.[...] 2007-05-11
_[36] 웹사이트 List of known prime rectangles for various polyominoes http://www.math.ucf.[...] 2007-05-11
_[37] 논문 Packing boxes with congruent figures
_[38] 웹사이트 A Finite Basis Theorem Revisited http://historical.nc[...] Stanford University Technical Report STAN-CS-73–338 1973-02
_[39] arXiv Tiling rectangles with holey polyominoes 2015
_[40] 논문 Tiling with Polyominoes
_[41] 웹사이트 Hard Tiling Problems with Simple Tiles http://www.santafe.e[...]
_[42] 간행물 Math Trek: Tiling with Polyominoes http://www.sciencene[...] 2012-03-11
_[43] 논문 On the relation between mathematics and the ordered patterns of Op art 1965-07
_[44] 논문 Thoughts on the task of communication with intelligent organisms on other worlds 1965-08
_[45] 논문 More about tiling the plane: the possibilities of polyominoes, polyiamonds and polyhexes 1975-08
_[46] 논문 Tiling complexity of small ''n''-ominoes
(''n''<10)
_[47] 서적 Planar Tilings and the Search for an Aperiodic Prototile PhD dissertation, Rutgers University
_[48] 문서 Grünbaum and Shephard, section 9.4
_[49] 논문 Isohedral Polyomino Tiling of the Plane
_[50] 논문 Planar tilings by polyominoes, polyhexes, and polyiamonds
_[51] 간행물 MASS selecta American Mathematical Society
_[52] 웹사이트 Mireles, J.L., "Poly2ominoes" https://web.archive.[...]
_[53] 웹사이트 Resta, G., "Polypolyominoes" http://www.iread.it/[...] 2010-07-02
_[54] 웹사이트 Zucca, L., "Triple Pentominoes" http://sicherman.net[...] 2023-04-20
_[55] 서적 Tribute to a Mathemagician A.K. Peters
_[56] 문서 Oxford English Dictionary, 2nd edition, entry ''domino''
_[57] 웹사이트 21-110: Polyominoes Introduction https://www.math.cmu[...] 2023-11-10
_[58] 웹사이트 Greek Numerical Prefixes http://www.georgehar[...]
_[59] 문서 芦ヶ原伸之『パズラート パズルの回帰線』P.72
_[60] OEIS A000105
_[61] OEIS A000988
_[62] OEIS A001168
_[63] 서적 数理パズル 中公新書
_[64] 웹사이트 http://www.hanayamat[...]
_[65] 웹사이트 明治チョコレートパズル https://www.hanayama[...] 2023-11-10