폴리오미노(Polyomino)는 평면 기하학에서 하나 이상의 동일한 단위 정사각형을 변과 변이 완전히 맞닿도록 연결하여 만들 수 있는 연결된 도형을 말한다. 이는 도미노(두 개의 정사각형)의 개념을 일반화한 것으로, 구성하는 정사각형의 개수에 따라 다양한 이름이 붙는다.
정의 폴리오미노는 다음 조건을 만족하는 평면상의 도형이다:
- 모두 동일한 크기의 단위 정사각형으로 구성된다.
- 각 정사각형은 적어도 한 변이 다른 정사각형과 완전히 맞닿아 연결되어야 한다 (점이나 부분적인 변 접촉은 허용되지 않음).
- 모든 정사각형이 연결되어 하나의 연속된 조각을 이룬다.
- 일반적으로 회전이나 대칭 이동을 통해 서로 일치하는 도형은 같은 폴리오미노로 간주한다 (자유 폴리오미노). 특정 문제에서는 고정된 방향의 폴리오미노나 한쪽 면만 고려하는 경우도 있다.
어원 및 역사 "폴리오미노"라는 용어는 1953년 미국의 수학자 솔로몬 W. 골롬(Solomon W. Golomb)이 미국 수학회(American Mathematical Society) 회의에서 발표한 것을 계기로 널리 알려졌다. 그는 이 개념을 대중화시키고 체계적으로 연구했으며, 1965년에 『폴리오미노: 퍼즐, 문제, 타일링』(Polyominoes: Puzzles, Problems, Problems, and Tilings)이라는 책을 출간했다. '폴리-' 접두사는 그리스어에서 유래한 것으로 '많은'을 의미하고, '-오미노'는 '도미노'(두 개의 정사각형)에서 파생되었다.
분류 폴리오미노는 구성하는 단위 정사각형의 개수(n)에 따라 다음과 같이 분류된다.
- 모노미노(Monomino, n=1): 단 하나의 정사각형.
- 도미노(Domino, n=2): 두 개의 정사각형. (1가지 형태)
- 트로미노 또는 트리미노(Tromino/Trimino, n=3): 세 개의 정사각형. (2가지 형태)
- 테트로미노(Tetromino, n=4): 네 개의 정사각형. (5가지 형태, 유명한 게임 테트리스에 사용됨)
- 펜토미노(Pentomino, n=5): 다섯 개의 정사각형. (12가지 형태, 유명한 퍼즐의 소재)
- 헥소미노(Hexomino, n=6): 여섯 개의 정사각형. (35가지 형태)
- 헵토미노 또는 셉토미노(Heptomino/Septomino, n=7): 일곱 개의 정사각형. (108가지 형태)
- 옥토미노(Octomino, n=8): 여덟 개의 정사각형. (369가지 형태) 이후로도 노노미노(n=9), 데코미노(n=10) 등으로 이어진다.
응용 및 퍼즐 폴리오미노는 조합론적 퍼즐과 게임에서 광범위하게 사용된다.
- 테트리스(Tetris): 가장 유명한 비디오 게임 중 하나로, 낙하하는 테트로미노 조각들을 빈틈없이 쌓아 올려 점수를 얻는 방식이다.
- 펜토미노 퍼즐: 12가지 펜토미노 조각 전체를 사용하여 직사각형이나 다른 지정된 모양을 빈틈없이 채우는 퍼즐이다. 다양한 변형이 존재하며, 수학적으로도 흥미로운 타일링 문제를 제공한다.
- 타일링 문제: 주어진 폴리오미노 세트로 특정 영역을 빈틈없이 채울 수 있는지, 또는 어떤 모양의 폴리오미노가 평면을 채울 수 있는지 등을 연구한다. 이는 수학, 컴퓨터 과학, 건축 등 다양한 분야에서 응용될 수 있다.
개수 세기 주어진 'n'개의 정사각형으로 만들 수 있는 서로 다른 폴리오미노의 개수를 세는 것은 조합론에서 중요한 문제이다. '서로 다른'을 정의하는 방식에 따라 개수가 달라진다.
- 자유 폴리오미노(Free polyominoes): 회전 및 대칭 이동(뒤집기)으로 일치하는 모든 도형을 하나로 간주한다. 가장 일반적으로 사용되는 정의이다.
- 한 면 폴리오미노(One-sided polyominoes): 회전만으로 일치하는 도형은 하나로 간주하지만, 대칭 이동(뒤집기)으로 일치하는 것은 별개로 간주한다.
- 고정 폴리오미노(Fixed polyominoes): 회전이나 대칭 이동을 고려하지 않고, 절대적인 위치와 방향이 다르면 모두 다른 도형으로 간주한다. 'n'이 커질수록 폴리오미노의 개수는 급격히 증가하며, 이를 정확히 계산하는 것은 복잡한 조합론적 문제이다.