룩 다항식

결합 수학에서, 루크 다항식은 비공격 루크를 체커보드처럼 보이는 보드에 배치하는 방법의 수를 생성하는 다항식이다. 즉, 두 루크가 같은 행이나 열에 있을 수 없다.보드는 m 행과 n개의 열이 있는 직사각형 보드의 정사각형 부분집합이다. 우리는 그것을 루크를 넣을 수 있는 정사각형이라고 생각한다.모든 사각형이 허용되고 m = n = 8이면 보드가 일반 체스판이고, 모든 사각형이 허용되고 m = n이면 어떤 크기의 체스판이다.루크 다항식 R_B(x)의 x ^k 계수는 k 루크가 다른 루크를 공격하지 않는 방법의 수로 B의 제곱에 배열할 수 없다.루크는 같은 행이나 열에 루크 쌍이 없는 방식으로 배열된다.이러한 의미에서 배치는 고정된 고정된 보드에 루크를 배치하는 것이다. 정사각형을 고정시키고 보드를 회전하거나 반사하는 경우 배치는 다르지 않을 것이다.행이 상호 교환되거나 열이 상호 교환되는 경우에도 다항식은 동일하게 유지된다.

rook 다항식이라는 용어는 John Riordan에 의해 만들어졌다.^[1]체스에서 유래된 이름임에도 불구하고, 신참 다항식을 연구하게 된 동기는 제한된 위치를 가진 순열(또는 부분 순열)을 세는 것과 관련이 있다.n × n 체스 보드의 하위 집합인 보드 B는 n개의 객체의 순열에 해당하며, 이 순열에서 j번째 위치에 있는 숫자 a가_j b의 j행에서 허용된 사각형의 열 번호가 되어야 하는 경우, 우리는 1, 2, ..., n으로 간주할 수 있다.유명한 예로는 n명의 비공격 루크를 배치하는 방법의 수가 있다.

• 기본적인 결합 문제인 전체 n × n 체스판
• 대각선 사각형이 금지된 동일한 보드; 이것은 변색 또는 "해트 체크" 문제(이것은 프로블렘 데 렌컨텐트의 특정한 경우);
• 대각선에 사각형이 없고 대각선 바로 위(그리고 왼쪽 하단 사각형 없음)가 없는 동일한 보드. 이것은 프로블렘 데스 메네지의 용액에 필수적이다.

루크 포지셔닝에 대한 관심은 순수하고 응용된 조합론, 집단 이론, 숫자 이론, 통계 물리학에서 발생한다.루크 다항식의 특별한 가치는 발생함수 접근방식의 효용성과 보드의 루크 다항식의 0이 그 계수에 대한 귀중한 정보, 즉 k 루크의 비공격적 배치의 수에서 비롯된다.

정의

보드 B의 루크 다항식 R_B(x)는 비공격 루크의 배열을 위한 생성 기능이다.

${\displaystyle R_{B}(x)=\sum _{k=0}^{\min{(m,n)}}r_{k}(B)x^{k}}}}}}}$

여기서 $r{\displaystyle {}_{}}$ ${\displaystyle k_{}}$( ${\displaystyle B}$) ${\displaystyle r_{k}(B)}$은(는) 비공격 루크를 보드 B에 배치하는 방법의 수입니다.보드가 보유할 수 있는 비공격 루크의 최대 수가 있다. 실제로 행 수나 보드의 열 수보다 많은 루크는 있을 수 없다(제한 ${\displaystyle 최소값(m}$ ${\displaystyle ,n}$) ${\displaystyle \min(m,n)}).$^[2]

완판

직사각형 m × n 보드 B의_m,n 경우 R_m,n := R_Bm,n, m=n이면 R := R이라고_nm,n 쓴다.

정사각형 n × n 보드의 처음 몇 개의 루크 다항식은 다음과 같다.

${\displaystyle {\reasoned}R_{1}(x)&=x+1\\R_{2}(x)&=2x^{2}+4x+1\\R_{3}(x)&=6x^{3}+18x^{2}+9x+1\\R_{4}(x)&=24x^{4}+96x^{3}+72x^{2}+16x+1\end{정렬}}}$

즉, 1 × 1 보드에서는 1 루크를 1 방향으로 배열할 수 있고, 0 루크를 1방향(빈 보드)으로 배열할 수 있으며, 전체 2 × 2 보드에서는 2방향(대각선 위), 1방향으로 1 루크를 배열할 수 있으며, 0 루크를 1방향으로 배열할 수 있다(대각선 위).

직사각형 체스판의 루크 다항식은 정체성에 의해 일반화된 라구에르 다항식_n^α L(x)와 밀접하게 관련되어 있다.

${\displaystyle R_{m,n}(x)=n!x^{n}L_{n}^{(m-n)}(-x^{-1})}$

일치하는 다항식

루크 다항식은 그래프에 있는 k-edge 일치 항목 수의 생성 함수인 일치하는 다항식의 한 종류의 특수한 경우다.

루크 다항식 R_m,n(x)은 완전한 초당적 그래프 K에_m,n 해당한다. 일반 보드 B의_m,n 루크 다항식은 정사각형(i, j)이 허용될 때마다 왼쪽 정점 v₁, v₂, ..., v_m 및 오른쪽 정점₁ w, w₂, ..., w_n, 엣지vw가_ij 있는 초당적 그래프에 해당한다.따라서, 신 다항식 이론은 어떤 의미에서 일치하는 다항식 이론에 포함되어 있다.

우리는 계수 r에_k 대한 중요한 사실을 추론하고, 우리가 B에서 k 루크의 공격하지 않는 위치 수를 고려하면, 이 숫자는 단수(unimodal), 즉, 최대치로 증가했다가 감소한다.이는 (표준 논리에 의해) 헤이일만과 렙의^[3] 정리로부터 일치하는 다항식(신선 다항식에 해당하지만 변수의 변화 하에서 그에 상당하는 그것과 다른 것)에 대한 0에 관한 것으로서, 이는 신선 다항식의 모든 0이 음의 실수임을 암시한다.

행렬 영속성에 대한 연결

불완전한 사각형 n × n 보드의 경우(즉, 이사회의 사각형의 일부 임의 하위 집합에서 루크를 재생할 수 없음) 보드에 n 루크를 배치하는 방법의 수를 계산하는 것은 0–1 행렬의 영구값을 계산하는 것과 같다.

직사각형 보드 완성

루크 문제

루크 다항식의 전구체는 H. E. Dudeney의^[4] 고전적인 "8명의 루크 문제"인데, 체스판 위의 비공격 루크의 최대 수는 주 대각선 중 하나에 올려서 8명이라는 것을 보여준다(그림 1).질문은 다음과 같다: "8×8 체스판에 8마리의 루크를 배치할 수 있는 방법이 몇 개인가?"답은 다음과 같다: "분명히 모든 행과 열에 루크가 있어야 한다.맨 아래 줄부터 시작하여 첫 번째 루크를 8개의 다른 사각형 중 하나에 놓을 수 있는 것이 분명하다(그림 1).어디에 놓든 2열에서 2루크에 7개의 정사각형을 선택할 수 있다.그러면 세 번째 행을 선택할 사각형이 여섯 개, 네 번째 행에 다섯 개, 등등이다.따라서 다른 방법의 수는 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)로 변환된다.루크를 다른 파일에 배치하려면 지금까지 두 번째 파일을 점유했던 루크를 첫 번째 루크가 비운 파일로 이동시켜야 한다.예를 들어 rok a1을"b"파일로 이동하면 rok b2를"를"파일로 이동해야 하며,이제 rokb1과 rok a2가 된다.새로운 순서는 (b,a,c,d,e,f,g,h)가 될 것이다.조합학에서는 이 연산을 순열이라고 하며 순열의 결과로 얻은 순열은 주어진 순열의 순열이다.8개 원소의 순서에서 8개 원소를 포함하는 순열의 총 수는 8! (요인 8개)이다.

"루크는 서로 공격해서는 안 된다"는 부과된 제한의 효과를 평가하기 위해, 그러한 제한 없이 문제를 고려한다.8 × 8 체스판에 8마리의 루크를 배치할 수 있는 방법은?이는 64개의 사각형에서 8개의 루크의 총 조합 수입니다.

${\displaystyle {64 \선택 8}={\frac {64!}{8!(64-8)!}}=4,426,165,368.}$

따라서 "루크는 서로 공격해서는 안 된다"는 한계는 조합에서 순열까지 허용 가능한 위치의 총 수를 감소시켜 약 109,776의 요인이다.

인간 활동의 서로 다른 영역에서 나온 여러 가지 문제들은 그들에게 "루크 제형"을 줌으로써 루크 문제로 줄어들 수 있다.예를 들면 다음과 같다.회사는 n개의 다른 직업에 n명의 노동자를 고용해야 하며 각각의 일은 한 명의 노동자에 의해서만 수행되어야 한다.이 약속은 몇 가지 방법으로 할 수 있는가?

노동자들을 N × n 체스판의 대열에 올려놓자. 그리고 그 일들-을 파일에 올려놓자.worker i가 job j에 임명되면, rock가 file j와 교차하는 광장에 look이 배치된다.각각의 일은 한 명의 노동자에 의해서만 수행되고 한 명의 노동자에 의해서만 임명되기 때문에, 모든 파일과 등급은 n명의 루크가 보드에 배치되어 한 명의 루크, 즉 루크는 서로 공격하지 않는다.

루크 문제의 일반화로서 루크 다항식

고전적인 루크 문제는 루크 다항식의 최고 순서 용어 앞에 있는 계수인 r 값을₈ 즉시 부여한다.실제로 비공격 루크 8마리를 8×8 체스보드에 r₈ = 8! = 40320 방식으로 배열할 수 있다는 결과가 나왔다.

m × n 보드, 즉 m 순위(행)와 n 파일(열)이 있는 보드를 고려하여 이 문제를 일반화하자.문제는 다음과 같다.k 루크는 m × n 보드에 서로 공격하지 않는 방식으로 몇 가지 방법으로 배열할 수 있는가?

문제가 해결되려면 k가 m과 n의 숫자보다 작거나 같아야 한다. 그렇지 않으면 한 쌍의 루크를 순위나 파일에 배치하지 않을 수 없다.이 조건을 충족시켜라.그러면 루크의 배치는 두 단계로 진행될 수 있다.먼저 루크를 배치할 k 순위 세트를 선택한다.순위 수는 m이므로 k를 선택해야 하므로 이 선택은${\displaystyle }$(${\displaystyle m\genfrac{}{}{0ex}{}{}{}}$ ${\displaystyle \genfrac{}{}{0ex}{}{k}{}}$) ${\$방법으로$$ 할 수 있다.마찬가지로, 루크를 배치할 k 파일 세트를${\displaystyle }$(${\displaystyle \genfrac{}{}{0ex}{}{n}{}}$k )$${\$displaystyle${\$binom {n}{k}}}$ 방법으로$$ 선택할 수 있다.파일의 선택은 순위 선택에 따라 달라지지 않기 때문에 제품 규칙에 따라 루크를 배치할 사각형을 선택하는 방법$$$({\displaystyle m\genfrac{}{}{0ex}{}{}{}}$ k${\displaystyle }$) ${\displaystyle (n\genfrac{}{}{0ex}{}{k}{}}$ ) (n ${\displaystyle \genfrac{}{}{0ex}{}{k}{}}$ ) ${\$이 있다.

그러나 k 순위와 k 파일이 k² 제곱에서 교차하기 때문에 아직 작업이 끝나지 않았다.사용되지 않은 순위 및 파일을 삭제하고 나머지 순위 및 파일을 압축함으로써 k 순위 및 k 파일의 새로운 보드를 얻는다.그러한 보드 k 루크는 (서로 공격하지 않도록) k! 방식으로 배치될 수 있다는 것은 이미 보여졌다.따라서 가능한 비공격 루크 배치의 총 수는 다음과 같다.^[6]

${\displaystyle r_{k}={\binom {m}{k}}{\binom {n}{k}}k!={\frac {n!m!}{{k!(n-k)!(m-k)!}}.}$

예를 들어, 3마리의 루크는 전통적인 체스판 (8 × 8)에 8${\displaystyle \frac{!}{}}$ ${\displaystyle \frac{8!}{}}$ ${\displaystyle \frac{\mathrm{}!}{}}$ ${\displaystyle \frac{5!}{}}$ ${\displaystyle \frac{5}{}}$= ${\displaystyle 18}$, ${\displaystyle 816}$ ${\$ {$8!8!)$에 놓일 수 있다.$}{3!5!5!$$}}}=18,816}$개의$$ 길.k = m = n의 경우, 위의 공식은 고전적인 루크 문제에 대해 얻은 결과에 해당하는_k r = n!을 제공한다.

명시적 계수를 갖는 루크 다항식은 이제 다음과 같다.

${\displaystyle R_{m,n(x)=\sum _{k=0}^{\min(m,n)}{k}{\binom {n}{k}{k!x^{k}=}=\sum _{k=0}^{k=0}{n,n!m!}{{k!(n-k)!(m-k)!}}}x^{k}.}$

"루크는 서로 공격해서는 안 된다"라는 한계가 제거되면 m × n 제곱에서 k 제곱을 선택해야 한다.이 작업은 다음에서 수행할 수 있다.

${\$$}{{k!(mn-k)!$$}}}$길$$

예를 들어, 라벨이 붙거나 번호가 매겨지는 등 k 루크가 서로 어떤 방식으로든 다를 경우 지금까지 얻은 모든 결과에 k 루크의 순열 수인 k!를 곱해야 한다.

대칭 배열

루크들의 문제를 더욱 복잡하게 만들기 위해 루크는 공격을 받지 않을 뿐만 아니라 보드에 대칭적으로 배치되어야 한다.대칭의 종류에 따라 회전하거나 보드를 반사하는 것과 같다.대칭 배치는 대칭 상태에 따라 많은 문제를 야기한다.^{[7][8][9][10]}

그러한 배열들 중 가장 간단한 것은 루크가 보드의 중심에 대칭적일 때 이다.g와_n 함께 n명의 루크가 n개의 순위 및 n개의 파일이 있는 보드에 배치되는 배열 수를 지정하자.이제 2n 순위 2n 파일 2n 파일로 이사회를 만들자.첫 번째 파일의 루크는 해당 파일의 2n 사각형 중 하나에 배치할 수 있다.대칭 조건에 따라, 이 루크의 배치는 마지막 파일에 서 있는 루크의 배치를 정의한다. 루크는 보드 중앙의 첫 번째 루크와 대칭적으로 배열되어야 한다.첫 번째와 마지막 파일, 그리고 루크가 차지하고 있는 순위를 제거하자(순위가 짝수인 만큼 제거된 루크는 같은 순위에 설 수 없다).이렇게 하면 2n - 2개의 파일과 2n - 2개의 순위가 부여된다.새 보드의 각 대칭적인 루크 배열은 원래 보드의 루크의 대칭적인 배열과 일치한다는 것은 분명하다.따라서 G_2n = 2nG_{2n − 2}(이 표현에서 2n 인수는 첫 번째 파일의 2n 사각형 중 하나를 첫 번째 루크가 차지할 가능성에서 나온다).위의 공식을 반복함으로써 2 × 2 보드의 경우에 도달한다. 그 위에 대칭 배열이 2개 있다(대각선 위).이 반복의 결과, 최종 표현은_2n G = 2nⁿ!일반적인 체스판(8 × 8)의 경우₈ G = 2⁴ × 4! = 16 × 24 = 384의 중심 대칭 배열 8 루크.그러한 배열 중 하나는 그림 2에 나와 있다.

홀수 크기 보드(2n + 1 순위 및 2n + 1 파일 포함)의 경우 대칭 이중성이 없는 사각형이 항상 존재하며, 이는 보드의 중앙 사각형이다.이 광장에는 항상 루크가 있어야 한다.중앙 파일과 순위를 제거하면 2n × 2n 보드에서 2n 루크의 대칭 배열을 얻는다.따라서 이러한 보드의 경우 다시_{2n + 1} 한번 G = G_2n = 2nⁿ!

좀 더 복잡한 문제는 보드를 90° 회전해도 변하지 않는 비공격 배열의 수를 찾는 것이다.보드에 4n 파일, 4n 순위를 두도록 하고, 루크의 수도 4n이다.이 경우 첫 번째 파일에 있는 루크는 코너 스퀘어를 제외하고 이 파일의 어떤 사각형도 점유할 수 있다(90° 회전 후 서로 공격하는 루크가 2명 있기 때문에 루크는 코너 스퀘어에 있을 수 없다).그 루크에 해당하는 루크가 3명 더 있고, 각각 마지막 순위, 마지막 순위, 1위 순위(첫 번째 루크에서 90°, 180°, 270° 회전)에 서 있다.이러한 루크의 파일 및 순위를 제거하면 필요한 대칭성을 가진 (4n - 4) × (4n - 4) 보드에 대한 루크 배열을 얻는다.따라서 다음과_4n 같은 반복 관계를 얻는다: R_{4n − 4} = (4n_n - 2)R, 여기서 R은 n × n 보드에 대한 배열 수입니다.Iterating, it follows that R_4n = 2n(2n − 1)(2n − 3)...1. The number of arrangements for a (4n + 1) × (4n + 1) board is the same as that for a 4n × 4n board; this is because on a (4n + 1) × (4n + 1) board, one rook must necessarily stand in the centre and thus the central rank and file can be removed.따라서 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이어야 한다.이것은_{4n + 2} R = R = 0임을_{4n + 3} 증명한다.

n × n 보드의 대각선 중 하나에 대칭되는 n 비공격 루크의 배열 수(결정성을 위해 체스보드의 a1–h8에 해당하는 대각선)는 재발_n Q = 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} 방법이 있는데, 이는 즉시 위와 같은 재발을 낳는다.대각선 대칭 배열의 수는 다음 식에 의해 주어진다.

${\displaystyle Q_{n}=1+{\binom {n}{2}}+{\frac {1}{1\times 2}}{\binom {n}{2}}{\binom {n-2}{2}}+{\frac {1}{1\times 2\times 3}}{\binom {n}{2}}{\binom {n-2}{2}}{\binom {n-4}{2}}+\cdots .}$

이 표현은 클래스의 모든 룩 배열을 분할하여 도출된다. 클래스 s는 s쌍의 루크가 대각선 상에 서지 않는 배열이다.정확히 같은 방법으로, n × n 보드의 n-rok 배열의 수는 서로 공격하지 않고 양쪽 대각선에 대칭되는 것으로서, 재발방정식 B_2n = 2B_{2n − 2} + (2n - 2)B와_{2n − 4} B_{2n + 1} = B에_2n 의해 주어지는 것을 알 수 있다.

대칭 등급별로 계산된 배열

다른 형태의 일반화는 보드의 대칭에 의해 서로 획득한 루크 배열을 하나로 계산하는 것이다.예를 들어, 대칭으로 보드를 90도 회전시킬 수 있다면, 90도, 180도 또는 270도의 회전으로 얻은 배열은 보드가 고정된 원래 문제에서 이러한 배열들이 별도로 계산되더라도, 원래의 패턴과 "동일한" 배열로 간주된다.그런 문제에 대해 두데니는^[11] "단순한 반전과 반성이 다른 것으로 계산되지 않는다면 얼마나 많은 방법이 있을 것인가, 그것은 어려운 문제"라고 관찰한다.문제는 번사이드의 보조정리기를 통해 대칭배열을 계산하는 것으로 줄어든다.

참조