루크 다항식

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 완전한 보드
3. 매칭 다항식과의 관계
4. 행렬 퍼머넌트와의 관계
5. 완전한 직사각형 보드
6. 대칭 클래스에 따른 배치 계산
참조

1. 개요

룩 다항식은 체스판과 같은 보드에서 서로 공격하지 않는 룩들의 배치 개수를 나타내는 생성 함수이다. 정의에 따르면, 룩 다항식은 보드에 k개의 룩을 배치하는 방법의 수를 계수로 가지는 다항식으로, 완전한 m × n 체스판의 룩 다항식은 라게르 다항식과 관련이 있다. 룩 다항식은 매칭 다항식의 특수한 경우이며, 행렬 퍼머넌트와도 연관된다. 룩 문제는 8 × 8 체스판에서 서로 공격하지 않는 8개의 룩을 배치하는 고전적인 문제이며, 일반화하여 m × n 보드에 k개의 룩을 배치하는 경우의 수를 계산할 수 있다. 또한, 룩을 체스판의 대칭에 따라 배치하는 문제도 연구되며, 중앙 대칭, 회전 대칭, 대각선 대칭 등 다양한 대칭 유형에 따른 룩 배치의 수를 계산할 수 있다. 룩 배치의 대칭 클래스에 따른 계산은 번사이드 보조정리를 통해 이루어진다.

더 읽어볼만한 페이지

수학적 체스 문제 - 맨해튼 거리
맨해튼 거리는 좌표축에 평행하게 측정한 거리 차이의 절댓값 합으로, 택시 기하학이라고도 불리며, 체스 룩의 이동이나 격자 도시 이동 거리 측정에 활용된다.
수학적 체스 문제 - 체비쇼프 거리
체비쇼프 거리는 두 벡터 또는 점 사이의 거리 측정 방식으로, 각 좌표 성분 차이의 절댓값 중 최댓값으로 정의되며 L∞ 거리라고도 불린다.
이산수학 - 고속 푸리에 변환
고속 푸리에 변환(FFT)은 이산 푸리에 변환(DFT)을 효율적으로 계산하는 알고리즘으로, 연산 횟수를 줄여 디지털 신호 처리, 이미지 처리, 음향 분석 등 다양한 분야에 활용되며 쿨리-튜키 알고리즘 등이 대표적이다.
이산수학 - 조합론
조합론은 이산적인 대상의 개수를 세거나 조건을 만족하는 대상을 구성, 분류하는 수학 분야로, 순열, 조합에서 시작해 그래프 이론, 설계 이론 등 다양한 조합적 구조와 관련된 문제를 연구하며 여러 학문 분야에 응용된다.
열거조합론 - 카탈랑 수
카탈랑 수는 조합론에서 여러 개수 세기 문제의 해답으로 나타나는 수열로, 괄호 구조, 이진 트리, 다각형 분할 등 다양한 조합론적 대상의 개수를 나타내며 여러 분야에 응용된다.
열거조합론 - 오일러 수 (조합론)
오일러 수는 조합론에서 집합의 순열 중 특정 조건을 만족하는 순열의 개수를 나타내는 수로, 주로 집합 $\{1,2,\ldots,n\}$ 의 순열에서 $a_i>a_{i+1}$ 인 $i$ 가 정확히 $m$ 개 있는 순열의 개수를 나타내며, 오일러 다항식 및 관련 성질과 함께 1755년 레온하르트 오일러에 의해 소개되었다.

2. 정의

보드 ''B''의 '''룩 다항식''' ''R''_''B''(''x'')는 서로 공격하지 않는 룩들의 배치 개수에 대한 생성 함수이다.

: $R_B(x)= \sum_{k=0}^{\min{(m,n)}} r_k(B) x^k,$

여기서 $r_k(B)$ 는 보드 ''B''에 ''k''개의 서로 공격하지 않는 룩을 배치하는 방법의 수이다. 보드가 가질 수 있는 서로 공격하지 않는 룩의 최대 개수가 있으며, 실제로 보드에 있는 행 또는 열의 수보다 더 많은 룩이 있을 수 없다(따라서 $\min(m,n)$ 의 제한).^[2]

2. 1. 완전한 보드

''m'' × ''n'' 체스판 ''B''_''m'',''n''에 대해, ''R_m,n'' := ''R''_{B_''m'',''n''}로 표기하며, ''m''=''n''일 경우 ''R_n'' := ''R''_''m'',''n''로 표기한다.

정사각형 ''n'' × ''n'' 체스판에서 처음 몇 개의 룩 다항식은 다음과 같다.

:

```

R₁(x) = x + 1

R₂(x) = 2x² + 4x + 1

R₃(x) = 6x³ + 18x² + 9x + 1

R₄(x) = 24x⁴ + 96x³ + 72x² + 16x + 1

```

이는 1 × 1 체스판에서는 1개의 룩을 1가지 방법으로, 0개의 룩을 1가지 방법(빈 체스판)으로 배치할 수 있음을 의미한다. 2 × 2 체스판에서는 2개의 룩을 2가지 방법(대각선)으로, 1개의 룩을 4가지 방법으로, 0개의 룩을 1가지 방법으로 배치할 수 있다. 더 큰 체스판에 대해서도 유사한 방식으로 룩을 배치할 수 있다.

직사각형 체스판의 룩 다항식은 일반화된 라게르 다항식 ''L''_''n''^''α''(''x'')와 다음 항등식을 통해 밀접하게 관련되어 있다.

:''R_m,n(x)''= ''n''! ''x''ⁿ''L''_n^{(''m''-''n'')}(-''x''^-1).

3. 매칭 다항식과의 관계

룩 다항식은 매칭 다항식의 특수한 경우이며, 그래프에서 ''k''개의 매칭의 개수를 생성하는 함수이다.^[3] 룩 다항식 ''R''_''m'',''n''(''x'')는 완전 이분 그래프 ''K''_''m'',''n''에 해당한다.^[3] 일반적인 보드 ''B'' ⊆ ''B''_''m'',''n''의 룩 다항식은 왼쪽 정점 ''v''₁, ''v''₂, ..., ''v''_''m''과 오른쪽 정점 ''w''₁, ''w''₂, ..., ''w''_''n''을 가지며, 사각형 (''i'', ''j'')가 ''B''에 속하는 경우에만 간선 ''v''_''i''''w''_''j''를 갖는 이분 그래프에 해당한다. 따라서 룩 다항식 이론은 매칭 다항식 이론에 포함된다.^[3]

''B''에서 공격받지 않는 ''k''개의 룩의 배치 수를 나타내는 계수 ''r''_''k''는 단봉이다.^[3] 즉, 최대값까지 증가한 다음 감소한다. 이는 룩 다항식의 모든 영점이 음수 실수임을 의미하는 Heilmann과 Lieb의 정리에 따른 것이다.^[3]

4. 행렬 퍼머넌트와의 관계

불완전한 정사각 행렬 ''n''×''n'' 보드(즉, 보드의 일부 임의의 사각형에 룩을 놓을 수 없음)의 경우, 보드에 ''n''개의 룩을 배치하는 방법의 수를 계산하는 것은 0–1 행렬의 퍼머넌트를 계산하는 것과 같다.

5. 완전한 직사각형 보드

5. 1. 룩 문제

H. E. 듀드니^[4]가 제시한 고전적인 "8 룩 문제"는 체스판에서 서로 공격하지 않는 룩의 최대 수가 8개임을 보여준다. 8 × 8 체스판에서 룩을 서로 공격하지 않게 배치하는 방법은 주 대각선 중 하나에 배치하는 것이다.

8 × 8 체스판에 서로 공격하지 않도록 8개의 룩을 배치하는 방법은 다음과 같이 구할 수 있다. 먼저, 각 행과 각 열에 룩이 하나씩 있어야 한다. 맨 아래 행부터 시작하면 첫 번째 룩을 8개의 다른 사각형 중 하나에 놓을 수 있다. 룩을 어디에 놓든 두 번째 행에 두 번째 룩을 놓을 수 있는 7개의 사각형이 남는다. 세 번째 행에는 6개, 네 번째 행에는 5개, 이런 식으로 계속해서 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320가지, 즉 8! (계승)가지의 방법이 있다.^[5]

다른 방법으로, 각 룩에 랭크 번호에 해당하는 위치 번호를 부여하고 파일 이름에 해당하는 이름을 지정할 수 있다. 예를 들어, 룩 a1은 위치 1과 이름 "a"를 갖고, 룩 b2는 위치 2와 이름 "b"를 갖는다. 룩을 위치에 따라 정렬된 목록(수열)으로 정렬하면, 그림 1의 배치는 (a,b,c,d,e,f,g,h)가 된다. 룩의 배치를 바꾸는 것은 이 수열의 순열을 구하는 것과 같으므로, 가능한 배치의 수는 8!이다.

"룩이 서로 공격해서는 안 된다"는 제한이 없는 경우, 8 × 8 체스판에 8개의 룩을 배치하는 방법은 64개의 사각형에서 8개를 선택하는 조합의 수와 같다.

:math {64 \choose 8} = \frac{64!}{8!(64-8)!} = 4,426,165,368.

따라서 "룩이 서로 공격해서는 안 된다"는 제한은 허용 가능한 위치의 총 수를 약 109,776배 감소시킨다.

룩 문제는 한 회사가 ''n''개의 서로 다른 직책에 ''n''명의 직원을 고용하는 문제와 같이 서로 다른 영역의 문제에도 적용될 수 있다. 직원 ''i''가 직책 ''j''에 임명되면 랭크 ''i''와 파일 ''j''가 교차하는 사각형에 룩을 배치하는 것으로 생각할 수 있다. 각 직책은 한 명의 직원에 의해서만 수행되고 각 직원은 하나의 직책에만 임명되므로, 룩은 서로 공격하지 않게 배치된다.

5. 2. 룩 문제의 일반화

''m'' × ''n'' 보드에 ''k''개의 룩을 서로 공격하지 않도록 배치하는 경우의 수는 다음과 같다.^[6]

:

r_k = \binom{m}{k}\binom{n}{k} k! = \frac{n! m!}{k! (n-k)! (m-k)!}.

예를 들어, 3개의 룩은 기존 체스판(8 × 8)에

\textstyle{\frac{8! 8!}{3!5!5!}} = 18,816

가지 방법으로 놓을 수 있다.

명시적 계수를 갖는 룩 다항식은 다음과 같다.^[6]

:

R_{m,n}(x) = \sum_{k=0}^{\min(m,n)} \binom{m}{k} \binom{n}{k} k! x^k = \sum_{k=0}^{\min(m,n)}\frac{n! m!}{k! (n-k)! (m-k)!} x^k.

만약 ''k''개의 룩이 서로 다른 방식으로, 예를 들어 라벨이 붙어 있거나 번호가 매겨져 있다면, 지금까지 얻은 모든 결과에 ''k''!, 즉 ''k''개의 룩의 순열 수를 곱해야 한다.

5. 3. 대칭적인 배치

룩이 서로 공격하지 않을 뿐만 아니라 체스판 위에서 대칭적으로 배치되도록 요구하는 문제도 고려할 수 있다.^[7]^[8]^[9]^[10] 대칭 유형에 따라 체스판을 회전하거나 반사하는 것과 동일하게 만들 수 있다.

이러한 배치 중 가장 간단한 것은 룩이 체스판의 중앙에 대해 대칭적으로 배치될 때이다. ''G_n''으로 ''n''개의 룩이 ''n''개의 행과 ''n''개의 열이 있는 체스판에 배치되는 배치의 수를 지정한다. 2''n'' × 2''n'' 체스판에서 첫 번째 열에 있는 룩은 해당 열의 2''n''개의 칸 중 아무 곳에나 놓을 수 있다. 대칭 조건에 따르면, 이 룩의 배치는 마지막 열에 있는 룩의 배치를 정의하며, 이 룩은 체스판의 중심에 대해 첫 번째 룩과 대칭적으로 배치되어야 한다. 첫 번째 열과 마지막 열, 그리고 룩이 차지하는 행을 제거하면 2''n'' − 2개의 열과 2''n'' − 2개의 행을 가진 체스판이 생성된다. 새로운 체스판에 있는 각 대칭 룩 배치에 대해 원래 체스판에 있는 대칭 룩 배치가 대응된다. 따라서 ''G''_2''n'' = 2''nG''_{2''n'' − 2} 이다. (이 표현식에서 2''n''이라는 요소는 첫 번째 룩이 첫 번째 열의 2''n''개의 칸 중 임의의 칸을 차지할 수 있기 때문에 나온다). 위의 공식을 반복하면 2 × 2 체스판의 경우에 도달하며, 여기에는 2개의 대칭 배치(대각선에)가 있다. 이 반복의 결과로 최종 표현식은 ''G''_2''n'' = 2^''n''''n''!이다. 일반적인 체스판(8 × 8)의 경우, ''G''₈ = 2⁴ × 4! = 16 × 24 = 384개의 8개의 룩의 중앙 대칭 배치이다. 이러한 배치의 예가 그림 2에 나와 있다.

홀수 크기의 체스판(2''n'' + 1개의 행과 2''n'' + 1개의 열 포함)의 경우, 항상 대칭 이중이 없는 칸이 있는데, 이는 체스판의 중앙 칸이다. 이 칸에는 항상 룩이 배치되어 있어야 한다. 중앙 열과 행을 제거하면 2''n'' × 2''n'' 체스판에 2''n''개의 룩이 대칭적으로 배치된다. 따라서 이러한 체스판의 경우에도 ''G''_2''n'' + 1 = ''G''_2''n'' = 2^''n''''n''!이다.

조금 더 복잡한 문제는 체스판을 90° 회전해도 변경되지 않는 비공격 배치의 수를 찾는 것이다. 4''n'' × 4''n'' 체스판에서 첫 번째 열에 있는 룩은 코너 칸을 제외하고 이 열의 어떤 칸이든 차지할 수 있다. 해당 루크에 해당하는 다른 3개의 룩이 있으며, 각각 마지막 행, 마지막 열 및 첫 번째 행에 있다 (이들은 90°, 180°, 270° 회전을 통해 첫 번째 룩에서 얻어진다). 해당 루크의 열과 행을 제거하면, (4''n'' − 4) × (4''n'' − 4) 체스판에 대한 루크 배치를 얻는다. 따라서, ''R''_4''n'' = (4''n'' − 2)''R''_{4''n'' − 4} 점화식이 얻어진다. 여기서 ''R_n''은 ''n'' × ''n'' 체스판에 대한 배치의 수이다. 반복하면 ''R''_4''n'' = 2''n''(2''n'' − 1)(2''n'' − 3)...1이 된다. (4''n'' + 1) × (4''n'' + 1) 체스판의 배치의 수는 4''n'' × 4''n'' 체스판의 배치의 수와 동일하며, 이는 (4''n'' + 1) × (4''n'' + 1) 체스판에서 한 룩이 반드시 중앙에 서야 하므로 중앙 행과 열을 제거할 수 있기 때문이다. 따라서 ''R''_4''n'' + 1 = ''R''_4''n''이다. 전통적인 체스판(''n'' = 2)의 경우, 회전 대칭을 갖는 가능한 배치는 ''R''₈ = 4 × 3 × 1 = 12개이다.

(4''n'' + 2) × (4''n'' + 2) 및 (4''n'' + 3) × (4''n'' + 3) 체스판의 경우, 해의 수는 0이다. 각 룩에 대해 두 가지 경우가 가능하다: 중앙에 서거나 중앙에 서지 않는다. 두 번째 경우, 이 룩은 체스판을 90° 돌릴 때 칸을 교환하는 루크 4중주에 포함된다. 따라서 루크의 총 수는 4''n''이거나(체스판에 중앙 칸이 없을 때) 4''n'' + 1이어야 한다. 이는 ''R''_4''n'' + 2 = ''R''_4''n'' + 3 = 0임을 증명한다.

''n'' × ''n'' 체스판에서 대각선 중 하나(a1–h8 대각선)에 대해 대칭적인 서로 공격하지 않는 ''n''개의 룩 배치의 수는 전화번호로 주어지며, 이는 ''Q''_''n'' = ''Q''_{''n'' − 1} + (''n'' − 1)''Q''_{''n'' − 2}의 점화식으로 정의된다. 첫 번째 열의 룩은 맨 아래 코너 칸에 있거나 다른 칸에 있다. 첫 번째 경우, 첫 번째 열과 첫 번째 행을 제거하면 (''n'' − 1) × (''n'' − 1) 체스판에 ''n'' − 1개의 룩이 대칭적으로 배치된다. 이러한 배치의 수는 ''Q''_{''n'' − 1}이다. 두 번째 경우, 원래 룩에 대해 선택된 대각선에 대해 첫 번째 룩과 대칭적인 다른 룩이 있다. 해당 루크의 열과 행을 제거하면 (''n'' − 2) × (''n'' − 2) 체스판에 ''n'' − 2개의 룩이 대칭적으로 배치된다. 이러한 배치의 수는 ''Q''_{''n'' − 2}이고, 루크는 첫 번째 열의 ''n'' − 1번째 칸에 놓을 수 있으므로, 이를 수행하는 방법은 (''n'' − 1)''Q''_{''n'' − 2}이므로, ''Q''_''n'' = ''Q''_{''n'' − 1} + (''n'' − 1)''Q''_{''n'' − 2} 점화식이 얻어진다.

서로 공격하지 않고 두 대각선에 대해 대칭적인 ''n'' × ''n'' 체스판의 ''n''-루크 배치의 수는 ''B''_2''n'' = 2''B''_{2''n'' − 2} + (2''n'' − 2)''B''_{2''n'' − 4} 및 ''B''_2''n'' + 1 = ''B''_2''n''의 점화식으로 주어진다.

5. 3. 1. 중앙 대칭

''n''개의 룩이 ''n'' × ''n'' 체스판의 중앙에 대해 대칭적으로 배치되는 경우의 수 ''G''_n''은 다음과 같다.

5. 3. 2. 회전 대칭

회전 대칭에 대한 내용은 주어진 원본 소스에 존재하지 않습니다.

5. 3. 3. 대각선 대칭

''n'' × ''n'' 체스판에서 대각선 중 하나에 대해 대칭적인 서로 공격하지 않는 ''n''개의 룩 배치의 수는 전화번호로 주어진다.

6. 대칭 클래스에 따른 배치 계산

보드의 대칭에 의해 서로 얻어지는 룩 배치들을 하나로 간주하는 경우의 수를 계산할 수 있다.^[11] 예를 들어, 보드를 90도 회전하는 것이 대칭으로 허용된다면, 90도, 180도, 또는 270도 회전에 의해 얻어지는 모든 배치는 보드가 고정된 원래 문제에서는 이러한 배치들이 별도로 계산됨에도 불구하고, 원래 패턴과 "같다"고 간주된다. 이 문제는 번사이드 보조정리를 통해 대칭 배치를 계산하는 문제로 축소된다.

참조

_[1] 서적 Introduction to Combinatorial Analysis https://books.google[...] Princeton University Press 1980
_[2] 웹사이트 Rook Polynomial http://mathworld.wol[...]
_[3] 논문 Theory of monomer-dimer systems 1972
_[4] 서적 Amusements In Mathematics https://www.gutenber[...] Nelson 1917
_[5] 문서 Dudeney, Problem 295
_[6] 서적 Combinatorics (Kombinatorika) Nauka Publishers, Moscow 1969
_[7] 서적 Popular Combinatorics (Populyarnaya kombinatorika) Nauka Publishers, Moscow 1975
_[8] 서적 Mathematics on the Chessboard (Matematika na shakhmatnoy doske) Nauka Publishers, Moscow 1976
_[9] 서적 Chess and Mathematics (Shakhmaty i matematika) http://gso.gbv.de Nauka Publishers, Moscow 1983
_[10] 간행물 Rook Numbers and Polynomials (Ladeynye chisla i mnogochleny) https://www.mccme.ru[...] MCNMO, Moscow 2003
_[11] 문서 Dudeney, Answer to Problem 295

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com