폴리오미노

Polyomino
"Polyominoes"는 여기서 리다이렉트 됩니다.Solomon Golomb의 책은 Polyominoes: Puzzle, Patterns, Problems, and Packings를 참조하십시오.
미러 페어 6개를 포함한 18개의 단면 펜토미노
35개의 자유로운 헥소미노는 대칭에 따라 색상이 매겨집니다.
싱글 프리 도미노.

폴리오미노는 1개 이상의 동일한 정사각형 모서리를 모서리에 접합하여 형성되는 평면 기하학적 도형이다.그것은 셀이 정사각형인 폴리폼이다.이는 정사각형 타일링의 유한 부분 집합으로 간주될 수 있다.

폴리오미노는 적어도 1907년부터 인기 있는 퍼즐에 사용되어 왔으며 펜토미노의 열거는 [1]고대로 거슬러 올라간다.1에서 6개의 정사각형 조각으로 이루어진 많은 결과들이 1937년에서 1957년 사이에 "해부 문제"라는 이름으로 페어리 체스 리뷰에 처음 발표되었습니다.폴리오미노라는 이름은 1953년 [2]솔로몬 W. 골롬에 의해 발명되었고, 마틴 가드너에 의해 1960년 11월 사이언티픽 [3]아메리칸의 "수학 게임" 칼럼에서 대중화 되었다.

폴리오미노와 관련된 것은 정삼각형으로 이루어진 폴리이아몬드, 정육각형으로 이루어진 폴리헥사스, 그리고 다른 평면 다형이다.폴리오미노는 큐브를 결합하여 폴리큐브를 형성하거나 하이퍼큐브를 결합하여 폴리큐브를 형성함으로써 더 높은 차원으로 일반화되었습니다.

통계 물리학에서, 폴리오미노와 그들의 고차원 아날로그에 대한 연구는 물리학과 화학의 문제에 적용된다.폴리오미노는 분기 폴리머와 침투 [4]클러스터의 모델로 사용되어 왔다.

레크리에이션 수학의 많은 퍼즐처럼 폴리오미노는 많은 조합 문제를 일으킨다.가장 기본적인 것은 주어진 크기의 폴리오미노를 열거하는 것이다.특별한 종류의 폴리오미노 외에는 어떤 공식도 발견되지 않았다.다수의 추정치가 알려져 있으며 이를 계산하기 위한 알고리즘이 있습니다.

구멍이 뚫린 폴리오미노는 타일링 문제 등 몇 가지 용도로는 불편합니다.일부 컨텍스트에서는 구멍이 있는 폴리오미노는 제외되며 단순히 연결된 [5]폴리오미노만 허용됩니다.

폴리오미노 열거

자유, 단측, 고정 폴리오미노

열거를 [6][7]위해 폴리오미노를 구별하는 일반적인 방법은 세 가지가 있습니다.

  • 자유 폴리오미노는 다른 것(집어서 뒤집을 수 있는 조각)의 단단한 변환(회전, 반사 또는 활공 반사)이 없을 때 구별됩니다.자유 폴리오미노를 반사하여 번역, 회전, 반사 또는 활공해도 모양이 바뀌지 않습니다.
  • 단측 폴리오미노는 다른 것을 번역하거나 회전하지 않을 때 구별됩니다(넘길 수 없는 조각).단측 폴리오미노를 번역하거나 회전해도 모양이 바뀌지 않습니다.
  • 고정 폴리오미노는 다른 것(뒤집거나 회전할 수 없는 조각)의 번역이 없을 때 구별됩니다.고정 폴리오미노를 번역해도 모양이 바뀌지 않습니다.

다음 표는 n개의 세포를 가진 다양한 유형의 폴리오미노 수를 보여줍니다.

n 이름. 공짜 일방적인 고정된.
총 구멍이 뚫려 빈틈없이
1 모노미노 1 0 1 1 1
2 도미노 1 0 1 1 2
3 트로미노 2 0 2 2 6
4 테트로미노 5 0 5 7 19
5 펜토미노 12 0 12 18 63
6 헥소미노 35 0 35 60 216
7 헵토미노 108 1 107 196 760
8 옥토미노 369 6 363 704 2,725
9 미노 1,285 37 1,248 2,500 9,910
10 데코미노 4,655 195 4,460 9,189 36,446
11 언데코미노 17,073 979 16,094 33,896 135,268
12 도데코미노 63,600 4,663 58,937 126,759 505,861
OEIS 시퀀스 A000105 A001419 A000104 A000988 A001168

2004년 기준으로 Iwan Jensen은 최대 n = 56 – 약 6.915×[8]10까지31 고정 폴리오미노를 열거했다.

유리 폴리오미노는 2007년 토마스 올리베이라 에 [9]실바에 의해 최대 n=28까지, 2012년 시라카와 [10]도시히로에 의해 최대 n=45까지 열거되었다.

폴리오미노 대칭

이면체군4 D는 정사각형의 대칭군(대칭군)이다.이 그룹에는 네 번의 회전과 네 번의 반사가 포함됩니다.X축과 대각선 주위의 반사를 번갈아 가며 생성됩니다.1개의 자유 폴리오미노는 최대 8개의 고정 폴리오미노에 해당하며, 이는 D의 대칭4 아래 있는 이미지이다.그러나 이러한 이미지가 반드시 구별되는 것은 아닙니다. 자유 폴리오미노는 대칭이 클수록 고정 고정 이미지가 적습니다.따라서 D의 일부4 또는 모든 사소하지 않은 대칭에서 불변하는 자유 폴리오미노는 고정 폴리오미노 4, 2 또는 1에 불과할 수 있다.수학적으로, 유리 폴리오미노는 그룹4 D에 속하는 고정 폴리오미노의 당량 클래스이다.

폴리오미노는 다음과 같은 대칭을 [11]가질 수 있습니다. 이 대칭을 가진 폴리오미노에 필요한 최소 제곱수가 각 경우에 주어집니다.

  • 프리 폴리오미노당 고정 폴리오미노 8개:
    • 대칭 없음(4)
  • 각 프리 폴리오미노에 대해 4개의 고정 폴리오미노:
    • 격자선 방향 중 하나에 대한 대칭(4)
    • 대각선에 대한 거울 대칭(3)
    • 2중 회전 대칭: C2(4)
  • 각 프리 폴리오미노에 대해 2개의 고정 폴리오미노:
    • 두 그리드 선 방향에 대한 대칭, 따라서 2중 회전 대칭: D2(2)(클라인 4그룹이라고도 함)
    • 양쪽 대각선 방향에 대한 대칭, 따라서 2배 회전 대칭: D2(7)
    • 4배 회전 대칭: C4(8)
  • 프리 폴리오미노 1개당 고정 폴리오미노 1개:
    • 정사각형의 모든 대칭: D4(1)

마찬가지로 단측 폴리오미노의 수는 다음과 같이 폴리오미노 대칭에 따라 달라집니다.

  • 각 프리 폴리오미노에 대해 2개의 단측 폴리오미노:
    • 무대칭
    • 2중 회전 대칭:C2.
    • 4배 회전 대칭:C4.
  • 각 프리 폴리오미노에 대해 1개의 단면 폴리오미노:
    • 정사각형의 모든 대칭:D4.
    • 격자선 방향 중 하나에 대한 대칭
    • 대각선에 대한 대칭
    • 두 그리드 라인 방향에 대한 대칭성, 즉 2중 회전 대칭성:D2.
    • 양쪽 대각선 방향에 대한 대칭, 따라서 2배 회전 대칭: D2.

다음 표는 대칭 그룹별로 정렬된 n개의 정사각형을 가진 폴리오미노 수를 보여 줍니다.

n 없음. 거울
90°		 거울
45°		 C2 D2
90°		 D2
45°		 C4 D4
1 0 0 0 0 0 0 0 1
2 0 0 0 0 1 0 0 0
3 0 0 1 0 1 0 0 0
4 1 1 0 1 1 0 0 1
5 5 2 2 1 1 0 0 1
6 20 6 2 5 2 0 0 0
7 84 9 7 4 3 1 0 0
8 316 23 5 18 4 1 1 1
9 1,196 38 26 19 4 0 0 2
10 4,461 90 22 73 8 1 0 0
11 16,750 147 91 73 10 2 0 0
12 62,878 341 79 278 15 3 3 3
OEIS 시퀀스 A006749 A006746 A006748 A006747 A056877 A056878 A144553 A142886

[12]

고정 폴리오미노 열거 알고리즘

유도 알고리즘

n차 폴리오미노에 정사각형을 더해 n+1차 폴리오미노를 얻을 수 있다.이를 통해 유도적으로 폴리오미노를 생성하는 알고리즘이 생성됩니다.

간단히 말해서, n차수의 폴리오미노 목록이 주어진 경우, 각 가능한 위치의 각 폴리오미노 옆에 정사각형을 추가할 수 있으며, n+1차수의 폴리오미노는 중복되지 않은 경우 목록에 추가할 수 있다. 고려해서는 안 되는 열거형의 순서와 인접 정사각형의 마킹이 개선되어 경우의 수가 감소한다.중복되지 [13]않았는지 확인해야 합니다.이 방법을 사용하여 자유 또는 고정 폴리오미노를 열거할 수 있습니다.

Redelmeier에 의해 기술된 보다 정교한 방법은 (n+1차수를 열거하기 위해 n차수의 모든 polyomino를 저장할 필요 없이) 폴리오미노를 셀 뿐만 아니라 그 숫자의 상한을 증명하는 방법으로 많은 저자에 의해 사용되어 왔다.기본 개념은 하나의 정사각형으로 시작하고 거기서부터 정사각형을 반복적으로 추가하는 것입니다.상세 내용에 따라 n개의 정사각형에서 1회씩 n회 카운트하거나 1회만 카운트하도록 배열할 수 있다.

가장 간단한 구현은 한 번에 한 칸씩 추가하는 것입니다.첫 번째 정사각형부터 시작하여 1, 2, 3, 4의 인접한 정사각형에 번호를 붙입니다.이제 1과 4 사이의 숫자를 선택하고 그 위치에 정사각형을 추가합니다.번호가 붙어 있지 않은 인접 사각형에 5부터 번호를 붙입니다.그런 다음 이전에 선택한 숫자보다 큰 숫자를 선택하고 그 정사각형을 더합니다.현재 정사각형 수보다 큰 숫자를 계속 선택하고 해당 정사각형을 추가한 다음 새 인접 정사각형의 번호를 매깁니다.n개의 정사각형이 작성되면 n-mino가 작성됩니다.

이 방법을 사용하면 각 고정 폴리오미노가 각 시작 정사각형에 대해 한 번씩 정확히 n번 카운트됩니다.각 폴리오미노를 n회 카운트하지 않고 1회 카운트하도록 최적화할 수 있습니다.첫 번째 정사각형부터 시작하여 폴리오미노의 왼쪽 아래 정사각형이라고 선언합니다.맨 아래 행에 있는 정사각형이나 같은 행에 있는 정사각형의 왼쪽에 있는 정사각형의 번호를 매기지 마십시오.이것은 Redelmeier가 설명한 버전입니다.

대신 자유 폴리오미노를 카운트하려면 각 n-미노를 작성한 후 대칭을 체크할 수 있습니다.그러나 대칭 폴리오미노를 개별적으로 생성하는 것이 더 빠르기[14] 때문에(이 [15]방법의 변형에 의해) 번사이드의 렘마에 의해 유리 폴리오미노 수를 결정한다.

전송행렬법

고정 폴리오미노를 열거하는 가장 현대적인 알고리즘은 Iwan Jensen에 [16]의해 발견되었다.Andrew Conway의 [17]방법을 개선하면 이전 방법보다 기하급수적으로 빨라집니다(다만 실행 시간은 여전히 n 단위로 기하급수적입니다).

Conway와 Jensen의 전달 매트릭스 방법 버전은 모두 특정 폭을 가진 폴리오미노의 수를 계수하는 것을 포함한다.모든 폭의 수를 계산하면 총 폴리오미노 수를 알 수 있습니다.이 방법의 기본 개념은 가능한 시작 행을 고려한 다음 주어진 폭의 폴리오미노를 완성하는 데 필요한 최소 제곱 수를 결정하는 것입니다.생성함수와 조합하여 여러 폴리오미노를 동시에 카운트할 수 있기 때문에 모든 폴리오미노를 생성해야 하는 방법보다 몇 배나 빠르게 실행할 수 있습니다.

실행 시간이 뛰어나지만 이 알고리즘은 기하급수적인 양의 메모리를 사용하며(n이 50을 초과하는 경우 수 기가바이트의 메모리가 필요), 다른 방법보다 프로그래밍이 훨씬 어려우며 현재 프리 폴리오미노를 카운트하는 데 사용할 수 없습니다.

폴리오미노 수의 점근적 증가

고정 폴리오미노

이론적인 주장과 수치 계산은 크기 n의 고정 폴리오미노 수에 대한 추정을 뒷받침한다.

여기서 = 4.0626, c = 0.3169이다.[18]그러나 이 결과는 입증되지 않았으며 θ와 c의 값은 추정치일 뿐이다.

알려진 이론적 결과는 이 추정치만큼 구체적이지 않다.라는 것이 증명되었다

즉, A는 기하급수적으로 성장한다n.2016년에 발견된 ,의 가장 잘 알려진 하한은 4.00253이다.[19]1970년대 이후 개선되지 않은 가장 잘 알려진 상한은 < < 4.[20]65입니다.

하한을 설정하기 위해 단순하지만 매우 효과적인 방법은 폴리오미노를 연결하는 것이다.오른쪽 상단 정사각형을 폴리오미노 맨 위 행의 맨 오른쪽 정사각형이 되도록 정의합니다.마찬가지로 왼쪽 아래 정사각형을 정의합니다.그리고 m사이즈의 임의의 폴리오미노의 왼쪽 아래 정사각형에 n사이즈의 임의의 폴리오미노의 오른쪽 상단 정사각형을 부착할 수 있어 독특한 (n+m)-미노를 생성할 수 있다.이것은 AA an+m A를 증명합니다nm.이 방정식을 사용하면 모든 n에 대해 1/nλ A를n 표시할 수 있습니다.이 절차를 A에 대한n 데이터와 결합하면 위에 제시된 하한이 생성됩니다.

상한은 폴리오미노를 열거하는 유도 방법을 일반화함으로써 달성된다.정사각형을 한 번에 하나씩 추가하는 대신 정사각형의 군집을 한 번에 추가합니다.이것은 종종 잔가지를 추가하는 것으로 묘사된다.모든 n-미노가 잔가지 계열임을 증명하고 가능한 잔가지 조합의 한계를 증명함으로써 n-미노 수의 상한을 얻는다.예를 들어, 위에서 설명한 알고리즘에서는 각 단계에서 더 큰 숫자를 선택해야 하며, 최대 3개의 새로운 숫자가 추가됩니다(최대 3개의 번호가 매겨지지 않은 정사각형에 인접해 있기 때문입니다).이 값을 사용하여 6.75의 상한을 얻을 수 있습니다.크라너와 리베스트는 280만 개의 잔가지로 상한선을 4.65로 잡았고, 이후 베어켓과 샬라에 의해 4.5252로 개선되었다.[21]

유리 폴리오미노

고정 폴리오미노 수와 유리 폴리오미노 수에 대한 근사치는 간단한 방식으로 관련된다.대칭(회전 또는 반사)이 없는 자유 폴리오미노는 8개의 개별 고정 폴리오미노에 해당하며, n이 클 경우 대부분의 n-오미노는 대칭이 없습니다.따라서 고정 n-미노 수는 자유 n-미노 수의 약 8배입니다.게다가 이 근사치는 n이 [11]증가할수록 기하급수적으로 정확해진다.

폴리오미노의 특수 클래스

정확한 공식은 볼록 폴리오미노 클래스 및 방향성 폴리오미노 클래스 등 특수 클래스의 폴리오미노를 열거하는 것으로 알려져 있다.

볼록한 폴리오미노의 정의는 볼록함에 대한 일반적인 정의와는 다르지만 직교 볼록한 선체에 사용되는 정의와 유사하다.폴리오미노는 수직선과의 교차가 볼록한 경우 수직 또는 기둥 볼록하다고 한다(즉, 각 기둥에는 구멍이 없다).마찬가지로 폴리오미노는 수평선과의 교차가 볼록하면 수평 또는 열 볼록하다고 한다.폴리오미노는 열과 행이 [22]볼록하면 볼록하다고 한다.

폴리오미노는 루트로 알려진 정사각형을 포함하고 있으며, 다른 모든 정사각형이 폴리오미노를 떠나지 않고 위 또는 오른쪽으로 한 정사각형을 움직이면 닿을 수 있다고 한다.

방향성 폴리오미노,[23] 열(또는 열) 볼록 폴리오미노 [24]및 볼록 폴리오미노는[25] 생성 함수를 사용하여 영역 n뿐만 아니라 주변과 같은 일부 다른 파라미터에 의해 효과적으로 열거되었다.

폴리오미노는 면적이 둘레와 같다면 동등합니다.균등한 폴리오미노는 짝수 제곱수로 만들어야 합니다. 15보다 큰 모든 짝수가 가능합니다.예를 들어, 4×4 정사각형 형태의 16-미노와 3×6 직사각형 형태의 18-미노 모두 동등하다.정사각형 수가 15개 미만인 폴리오미노의 경우 둘레는 항상 [26]면적을 초과합니다.

폴리오미노 타일링

레크리에이션 수학에서는, 소정의 영역 또는 평면 전체를 폴리오미노로 [27]타일링 하는 과제가 종종 제기되며, 수학과 컴퓨터 과학에서 관련 문제를 조사한다.

폴리오미노 세트가 있는 타일링 영역

퍼즐은 일반적으로 12개의 펜토미노와 같은 주어진 폴리오미노 세트로 주어진 영역을 타일링하는 것을 요구합니다.골롬과 가드너의 책에는 많은 예가 있다.전형적인 퍼즐은 6×10 직사각형에 12개의 펜토미노를 타일로 붙이는 것이다.[28] 이에 대한 2339 해법은 1960년에 발견되었다.세트 내 폴리오미노 복사가 여러 개 허용되는 경우 Golomb는 직사각형, 스트립 및 전체 평면 등 세트가 타일링할 수 있는 다른 영역의 계층을 정의하고 Wang 타일 세트를 폴리오미노 [29]세트에 매핑함으로써 특정 세트의 폴리오미노가 평면을 타일링할 수 있는지 여부를 결정할 수 없음을 보여 줍니다.

폴리오미노 세트로 평면을 타일링하는 일반적인 문제는 [30]NP-완전이기 때문에 여러 조각으로 타일링을 하는 것은 빠르게 다루기 어려워지기 때문에 컴퓨터의 도움이 필요하다.비행기의 유한한 영역을 타일링하는 전통적인 접근법은 [31]역추적이라 불리는 컴퓨터 과학 기술을 사용한다.

직소 수도쿠스에서 정사각형 그리드는 다항식 영역(OEIS의 시퀀스 A172477)으로 타일링됩니다.

단일 폴리오미노 복사본이 있는 타일링 영역

다른 종류의 문제에서는 특정 폴리오미노 복사본이 직사각형을 타일링할 수 있는지, 타일링할 [32]수 있는 직사각형을 질문합니다.이러한 문제는 특정 폴리오미노에 [33]대해 광범위하게 연구되어 개별 폴리오미노에 대한 결과표를 이용할 [34]수 있다.Clarner와 Göbel은 어떤 폴리오미노에도 유한한 수의 소수 직사각형이 있다는 것을 보여주었고, 그래서 다른 모든 직사각형이 그 [35][36]소수 직사각형에 의해 타일링될 수 있다.Kamenetsky와 Cooke는 다양한 분리된 폴리오미노가 어떻게 직사각형을 [37]타일링할 수 있는지를 보여주었다.

직사각형을 넘어 골롬은 단일 폴리오미노에 대한 계층을 부여했다: 폴리오미노는 직사각형, 하프스트립, 구부러진 스트립, 자신의 확대된 복사본, 사분면, 스트립, 하프플레인, 전체 평면, 특정 조합 또는 이들 중 어느 것도 타일링할 수 있다.이들 사이에는 분명한 의미가 있습니다(예를 들어 폴리오미노가 하프플레인을 타일링하면 전체 평면을 타일링합니다).그리고 그 이하(예를 들어 폴리오미노가 자신의 확대된 복사본을 타일링하면 사분면도 타일링합니다).이 계층에서는 최대 6개의 차수의 폴리오미노가 특징지어집니다(이 상태는 1개의 헥소미노로 나중에 직사각형 타일로 표시되어 그 시점에서 해결되지 않았습니다).[38]

2001년에 크리스토퍼 무어와 존 마이클 롭슨은 한 폴리오미노를 다른 폴리오미노와 결합시키는 문제는 [39][40]NP-완전하다는 것을 보여주었다.

단일 폴리오미노 복사본으로 평면 타일링

2개의 타일링 논노미노가 Conway 기준을 충족하지 않습니다.

단일 폴리오미노 복제품으로 비행기를 타일링하는 것 또한 많은 논의가 있었다.1965년에 [42]헥소미노까지[41] 모든 폴리오미노와 4개의 헵토미노를 제외한 모든 헵토미노가 비행기에 타일을 붙인다는 것이 발견되었다.그리고 나서 데이비드 버드에 의해 26개의 옥토미노를 제외한 모든 옥토미노가 비행기에 [43]타일을 붙이는 것이 확인되었다.Rawsthorne은 9번 [44]타일의 235개를 제외한 모든 폴리오미노가 발견되었으며, 이러한 결과는 Rhoads(14개 [45]주문)와 다른 사람들에 의해 더 높은 차수로 확장되었습니다.평면을 타일링하는 폴리오미노는 타일링의 대칭과 [46][47]타일이 나타나는 측면(방향)의 수에 따라 분류되었습니다.

어떤 폴리오미노가 평면을 타일링할 수 있는지에 대한 연구는 Conway 기준을 사용하여 촉진되었습니다. 즉, 두 개의 비오미노를 제외한 모든 타일링 폴리오미노는 적어도 하나의 타일을 만족시키는 패치를 형성하며, 고차 예외는 [48]더 자주 발생합니다.

여러 개의 폴리오미노는 자신의 더 큰 복사본을 타일링할 수 있으며, 이 과정을 반복하면 평면의 타일링이 반복됩니다.예를 들어 정의 정수 n마다 L-트로미노, L-테트로미노 또는 P-펜토미노의 n개의 복사본을 [49]그 생성원의 작은 폴리오미노와 유사한 하나의 큰 형상으로 조합할2 수 있다.

다양한 폴리오미노로 공통 피규어 타일링

T펜토미노와 W펜토미노의 최소한의 호환성 수치.

호환성 문제는 두 개 이상의 폴리오미노를 취하여 각각 타일링할 수 있는 수치를 찾는 것입니다.폴리오미노 적합성은 1990년대부터 널리 연구되어 왔다.Jorge Luis Mireles와 Giovanni Resta는 체계적인 [50][51]결과의 웹사이트를 공개했으며, Livio Zucca는 세 가지 다른 펜토미노와 [52]같은 복잡한 사례에 대한 결과를 보여주고 있다.일반적인 문제는 어려울 수 있습니다.L과 X 펜토미노에 대한 최초의 호환성 수치는 2005년에 발표되었으며 [53]각 종류의 80개의 타일이 있었다.많은 폴리오미노 쌍이 체계적인 소모로 인해 양립할 수 없는 것으로 입증되었습니다.2개의 임의의 폴리오미노가 호환성이 있는지 여부를 판단하는 알고리즘은 알려져 있지 않습니다.

퍼즐과 게임의 폴리오미노

위에서 설명한 타일 문제 외에도, 다른 모양을 만들기 위해 폴리오미노를 접어야 하는 레크리에이션용 수학 퍼즐이 있습니다.가드너는 무료 펜토미노 세트와 체스판이 있는 몇 가지 간단한 게임을 제안했다.스도쿠 퍼즐의 일부 변형은 그리드상의 비오미노형 영역을 사용합니다.비디오 게임 테트리스는 7개의 단측 테트로미노(게임 내에서는 테트로미노로 표기)를 기반으로 하고 있으며, 보드 게임 블로커스는 펜토미노까지 모든 자유 폴리오미노를 사용한다.

어원학

polyomino라는 단어와 polyomino의 다양한 순서의 이름은 모두 두 개의 정사각형으로 구성된 일반적인 게임 작품인 domino라는 단어에서 유래한 것이며, 첫 글자는 "둘"을 의미하는 접두사 di-의 버전으로 화려하게 해석된다.도미노라는 이름은 라틴 도미누스에서 [54]온 얼룩무늬 가면의류 도미노에서 유래한 것으로 알려져 있다.

숫자 접두사의 대부분은 그리스어입니다.순서 9와 11의 폴리오미노는 그리스 접두사 엔네오미노(enneomino)와 헨데카([why?]hendeca-)보다 라틴 접두사 nona-(nonomino)와 undecomino(undecomino)를 더 많이 사용한다.

「 」를 참조해 주세요.

  • 침투 이론, 정수 그리드의 무작위 하위 집합에 대한 수학적 연구입니다.이들 서브셋의 유한하게 연결된 구성요소는 폴리오미노를 형성합니다.
  • 영 다이어그램은 정수 분할을 기술하기 위해 수 이론에서 사용되는 특수한 종류의 폴리오미노이며, 대칭군의 표현을 기술하기 위해 수학 물리학의 군 이론 및 응용 분야에서 사용됩니다.
  • 폴리오미노를 이용한 보드 게임인 Blokus.
  • 정사각형 그래프, 폴리오미노의 꼭지점 및 모서리 그래프를 포함하는 일종의 무방향 그래프입니다.

메모들

  1. ^ 골롬(Polyominoes, First Edition의 서문)은 "고보드 위에 다섯 개의 연결된 돌에 의해 형성될 수 있는 12개의 독특한 패턴(펜토미노)이 있다는 관찰은 그 게임의 고대 거장 덕분이다"라고 쓰고 있다.
  2. ^ Golomb, Solomon W. (1994). Polyominoes (2nd ed.). Princeton, New Jersey: Princeton University Press. ISBN 978-0-691-02444-8.
  3. ^ Gardner, M. (November 1960). "More about the shapes that can be made with complex dominoes (Mathematical Games)". Scientific American. 203 (5): 186–201. doi:10.1038/scientificamerican1160-186. JSTOR 24940703.
  4. ^ Whittington, S. G.; Soteros, C. E. (1990). "Lattice Animals: Rigorous Results and Wild Guesses". In Grimmett, G.; Welsh, D. (eds.). Disorder in Physical Systems. Oxford University Press.
  5. ^ Grünbaum, Branko; Shephard, G.C. (1987). Tilings and Patterns. New York: W.H. Freeman and Company. ISBN 978-0-7167-1193-3.
  6. ^ Redelmeier, D. Hugh (1981). "Counting polyominoes: yet another attack". Discrete Mathematics. 36 (2): 191–203. doi:10.1016/0012-365X(81)90237-5.
  7. ^ 골롬, 6장
  8. ^ Iwan Jensen. "Series for lattice animals or polyominoes". Archived from the original on 2007-06-12. Retrieved 2007-05-06.
  9. ^ Tomás Oliveira e Silva. "Animal enumerations on the {4,4} Euclidean tiling". Archived from the original on 2007-04-23. Retrieved 2007-05-06.
  10. ^ "Harmonic Magic Square, Enumeration of Polyominoes considering the symmetry" (PDF).
  11. ^ a b 레델마이어, 섹션 3
  12. ^ 폴리오미노 카운트: 또 다른 공격
  13. ^ 골롬, 73-79페이지
  14. ^ 레델마이어, 섹션 4
  15. ^ 레델마이어, 섹션 6
  16. ^ Jensen, Iwan (February 2001). "Enumerations of Lattice Animals and Trees". Journal of Statistical Physics. 102 (3–4): 865–881. arXiv:cond-mat/0007239. Bibcode:2001JSP...102..865J. doi:10.1023/A:1004855020556. S2CID 10549375.
  17. ^ Conway, Andrew (1995). "Enumerating 2D percolation series by the finite-lattice method: theory". Journal of Physics A: Mathematical and General. 28 (2): 335–349. Bibcode:1995JPhA...28..335C. doi:10.1088/0305-4470/28/2/011. Zbl 0849.05003.
  18. ^ Jensen, Iwan; Guttmann, Anthony J. (2000). "Statistics of lattice animals (polyominoes) and polygons". Journal of Physics A: Mathematical and General. 33 (29): L257–L263. arXiv:cond-mat/0007238v1. Bibcode:2000JPhA...33L.257J. doi:10.1088/0305-4470/33/29/102. S2CID 6461687.
  19. ^ Barequet, Gill; Rote, Gunter; Shalah, Mira. "λ > 4: An Improved Lower Bound on the Growth Constant of Polyominoes". Retrieved 2017-02-02. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
  20. ^ Klarner, D.A.; Rivest, R.L. (1973). "A procedure for improving the upper bound for the number of n-ominoes" (PDF). Canadian Journal of Mathematics. 25 (3): 585–602. CiteSeerX 10.1.1.309.9151. doi:10.4153/CJM-1973-060-4. S2CID 121448572. Archived from the original (PDF of technical report version) on 2006-11-26. Retrieved 2007-05-11.
  21. ^ Barequet, Gill; Shalah, Mira (2022). "Improved upper bounds on the growth constants of polyominoes and polycubes". Algorithmica. doi:10.1007/s00453-022-00948-6.
  22. ^ Wilf, Herbert S. (1994). Generatingfunctionology (2nd ed.). Boston, MA: Academic Press. p. 151. ISBN 978-0-12-751956-2. Zbl 0831.05001.
  23. ^ Bousquet-Mélou, Mireille (1998). "New enumerative results on two-dimensional directed animals". Discrete Mathematics. 180 (1–3): 73–106. doi:10.1016/S0012-365X(97)00109-X.
  24. ^ Delest, M.-P. (1988). "Generating functions for column-convex polyominoes". Journal of Combinatorial Theory, Series A. 48 (1): 12–31. doi:10.1016/0097-3165(88)90071-4.
  25. ^ Bousquet-Mélou, Mireille; Fédou, Jean-Marc (1995). "The generating function of convex polyominoes: The resolution of a q-differential system". Discrete Mathematics. 137 (1–3): 53–75. doi:10.1016/0012-365X(93)E0161-V.
  26. ^ 를 클릭합니다Picciotto, Henri (1999), Geometry Labs, MathEducationPage.org, p. 208.
  27. ^ Martin, George E. (1996). Polyominoes: A guide to puzzles and problems in tiling (2nd ed.). Mathematical Association of America. ISBN 978-0-88385-501-0.
  28. ^ C.B. Haselgrove; Jenifer Haselgrove (October 1960). "A Computer Program for Pentominoes" (PDF). Eureka. 23: 16–18.
  29. ^ Golomb, Solomon W. (1970). "Tiling with Sets of Polyominoes". Journal of Combinatorial Theory. 9: 60–71. doi:10.1016/S0021-9800(70)80055-2.
  30. ^ E.D. Demaine; M.L. Demaine (June 2007). "Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity". Graphs and Combinatorics. 23: 195–208. doi:10.1007/s00373-007-0713-4. S2CID 17190810.
  31. ^ S.W. Golomb; L.D. Baumert (1965). "Backtrack Programming". Journal of the ACM. 12 (4): 516–524. doi:10.1145/321296.321300.
  32. ^ 골롬, 폴리오미노, 8장
  33. ^ Reid, Michael. "References for Rectifiable Polyominoes". Archived from the original on 2004-01-16. Retrieved 2007-05-11.
  34. ^ Reid, Michael. "List of known prime rectangles for various polyominoes". Archived from the original on 2007-04-16. Retrieved 2007-05-11.
  35. ^ Klarner, D.A.; Göbel, F. (1969). "Packing boxes with congruent figures". Indagationes Mathematicae. 31: 465–472.
  36. ^ Klarner, David A. (February 1973). "A Finite Basis Theorem Revisited" (PDF). Stanford University Technical Report STAN-CS-73–338. Archived from the original (PDF) on 2007-10-23. Retrieved 2007-05-12.
  37. ^ Kamenetsky, Dmitry; Cooke, Tristrom (2015). "Tiling rectangles with holey polyominoes". arXiv:1411.2699 [cs.CG].
  38. ^ Golomb, Solomon W. (1966). "Tiling with Polyominoes". Journal of Combinatorial Theory. 1 (2): 280–296. doi:10.1016/S0021-9800(66)80033-9.
  39. ^ Moore, Cristopher; Robson, John Michael (2001). "Hard Tiling Problems with Simple Tiles" (PDF). Archived from the original (PDF) on 2013-06-17.
  40. ^ 를 클릭합니다Petersen, Ivars (September 25, 1999), "Math Trek: Tiling with Polyominoes", Science News, archived from the original on March 20, 2008, retrieved March 11, 2012.
  41. ^ Gardner, Martin (July 1965). "On the relation between mathematics and the ordered patterns of Op art". Scientific American. 213 (1): 100–104. doi:10.1038/scientificamerican1265-100.
  42. ^ Gardner, Martin (August 1965). "Thoughts on the task of communication with intelligent organisms on other worlds". Scientific American. 213 (2): 96–100. doi:10.1038/scientificamerican0865-96.
  43. ^ Gardner, Martin (August 1975). "More about tiling the plane: the possibilities of polyominoes, polyiamonds and polyhexes". Scientific American. 233 (2): 112–115. doi:10.1038/scientificamerican0875-112.
  44. ^ Rawsthorne, Daniel A. (1988). "Tiling complexity of small n-ominoes
    (n<10)"    . Discrete Mathematics. 70: 71–75. doi:10.1016/0012-365X(88)90081-7.
  45. ^ Rhoads, Glenn C. (2003). Planar Tilings and the Search for an Aperiodic Prototile. PhD dissertation, Rutgers University.
  46. ^ Grünbaum and Shephard, 섹션 9.4
  47. ^ Keating, K.; Vince, A. (1999). "Isohedral Polyomino Tiling of the Plane". Discrete & Computational Geometry. 21 (4): 615–630. doi:10.1007/PL00009442.
  48. ^ Rhoads, Glenn C. (2005). "Planar tilings by polyominoes, polyhexes, and polyiamonds". Journal of Computational and Applied Mathematics. 174 (2): 329–353. Bibcode:2005JCoAM.174..329R. doi:10.1016/j.cam.2004.05.002.
  49. ^ Niţică, Viorel (2003). "Rep-tiles revisited". MASS selecta. Providence, RI: American Mathematical Society. pp. 205–217. MR 2027179.
  50. ^ 미렐스, J.L. '폴리오미노2'
  51. ^ "Resta, G., "Polypolyominoes"". Archived from the original on 2011-02-22. Retrieved 2010-07-02.
  52. ^ "Zucca, L., "Triple Pentominoes"". Archived from the original on 2012-03-15. Retrieved 2011-12-15.
  53. ^ Barbans, Uldis; Cibulis, Andris; Lee, Gilbert; Liu, Andy; Wainwright, Robert (2005). "Polyomino Number Theory (III)". In Cipra, Barry Arthur; Demaine, Erik D.; Demaine, Martin L.; Rodgers, Tom (eds.). Tribute to a Mathemagician. Wellesley, MA: A.K. Peters. pp. 131–136. ISBN 978-1-56881-204-5.
  54. ^ 옥스퍼드 영어사전, 제2판, 엔트리 도미노

외부 링크

온라인 폴리오미노 솔버

출판물