루크 다항식

1. 개요

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

2. 정의

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

: $R\_B(x)=\; \backslash sum\_\{k=0\}^\{\backslash min\{(m,n)\}\}\; r\_k(B)\; x^k,$

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

2.1. 완전한 보드

m × n 체스판 B_m,n에 대해, R_m,n := R_Bm,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개의 매칭의 개수를 생성하는 함수이다. 룩 다항식 R_m,n(x)는 완전 이분 그래프 K_m,n에 해당한다. 일반적인 보드 B ⊆ B_m,n의 룩 다항식은 왼쪽 정점 v₁, v₂, ..., v_m과 오른쪽 정점 w₁, w₂, ..., w_n을 가지며, 사각형 (i, j)가 B에 속하는 경우에만 간선 v_iw_j를 갖는 이분 그래프에 해당한다. 따라서 룩 다항식 이론은 매칭 다항식 이론에 포함된다.

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

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

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

5. 완전한 직사각형 보드

5.1. 룩 문제

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

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

다른 방법으로, 각 룩에 랭크 번호에 해당하는 위치 번호를 부여하고 파일 이름에 해당하는 이름을 지정할 수 있다. 예를 들어, 룩 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개의 룩을 서로 공격하지 않도록 배치하는 경우의 수는 다음과 같다.

:$r\_k\; =\; \backslash binom\{m\}\{k\}\backslash binom\{n\}\{k\}\; k!\; =\; \backslash frac\{n!\; m!\}\{k!\; (n-k)!\; (m-k)!\}.$

예를 들어, 3개의 룩은 기존 체스판(8 × 8)에 $\backslash textstyle\{\backslash frac\{8!\; 8!\}\{3!5!5!\}\}\; =\; 18,816$가지 방법으로 놓을 수 있다.

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

:$R\_\{m,n\}(x)\; =\; \backslash sum\_\{k=0\}^\{\backslash min(m,n)\}\; \backslash binom\{m\}\{k\}\; \backslash binom\{n\}\{k\}\; k!\; x^k\; =\; \backslash sum\_\{k=0\}^\{\backslash min(m,n)\}\backslash frac\{n!\; m!\}\{k!\; (n-k)!\; (m-k)!\}\; x^k.$

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

5.3. 대칭적인 배치

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

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

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

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

(4n + 2) × (4n + 2) 및 (4n + 3) × (4n + 3) 체스판의 경우, 해의 수는 0이다. 각 룩에 대해 두 가지 경우가 가능하다: 중앙에 서거나 중앙에 서지 않는다. 두 번째 경우, 이 룩은 체스판을 90° 돌릴 때 칸을 교환하는 루크 4중주에 포함된다. 따라서 루크의 총 수는 4n이거나(체스판에 중앙 칸이 없을 때) 4n + 1이어야 한다. 이는 R_4n + 2 = R_4n + 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_2n = 2B_2n − 2 + (2n − 2)B_2n − 4 및 B_2n + 1 = B_2n의 점화식으로 주어진다.

5.3.1. 중앙 대칭

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

5.3.2. 회전 대칭

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

5.3.3. 대각선 대칭

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

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

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