얼마나 $3\times 3$ 숫자가있는 배열 $1$ ...에 $9$ 증가하는 순서와 함께 있습니까?
의 항목 $3 \times 3$ 배열은 모든 자릿수를 포함합니다. $1$ ...을 통하여 $9$, 모든 행과 열의 항목이 오름차순으로 정렬됩니다. 그러한 어레이가 몇 개 있습니까?
이것은 조합론에 대한 질문입니다. 나는 tableaus를 사용하고 후크 번호를 사용하여 시도했지만 그 후에는 이해할 수 없었습니다.이 문제를 해결하는 방법을 알려주십시오. 정상적인 조합을 사용하여 해결하면 더 쉬울 것입니다. 그러나 제한은 없습니다. 당신의 선택입니다
답변
표기법 사용 $(A,B,C)$ 숫자를 설명하기 위해 $C$ 에 위치한 $A$ 행 및 $B$기둥. 대칭으로 인해 모든 솔루션의 전치 (주 대각선을 가로 지르는 반사)는 다른 솔루션입니다. 즉, 솔루션이있는 경우 :$$\{(A_1,B_1,1), (A_2,B_2,2), (A_3,B_3,3), (A_4,B_4,4), (A_5,B_5,5), (A_6,B_6,6), (A_7,B_7,7), (A_8,B_8,8), (A_9,B_9,9)\}$$ 그런 다음 해결책도 있습니다. $$\{(B_1,A_1,1), (B_2,A_2,2), (B_3,A_3,3), (B_4,A_4,4), (B_5,A_5,5), (B_6,A_6,6), (B_7,A_7,7), (B_8,A_8,8), (B_9,A_9,9)\}$$
모든 행과 열은 오름차순이어야하므로 솔루션에는 다음이 포함되어야합니다. $(1,1,1)$ 과 $(3,3,9)$.
번호를 어디에 넣을지 두 가지 선택이 있습니다. $8$. 대칭으로 인해 우리는$(3,2,8)$, 솔루션 수를 두 배로 늘리면됩니다.
우리는 이제 두 가지 선택이 있습니다. $7$:
사례 1 : $(3,1,7)$
수 $6$ 로 잠겨 있습니다. $(2,3,6)$. 수$5$ 다음 중 하나 일 수 있습니다. $(2,2,5)$ 또는 $(1,3,5)$. 만약$(2,2,5)$, 숫자 $2,3,4$나머지 세 자리에 있어야합니다. 어느 것이 있는지 선택하자마자$(2,1,X)$, 나머지는 제자리에 고정되어 $(3,1,7)$ 과 $(2,2,5)$. 만약$(1,3,5)$, 그러면 우리는 $(2,2,4)$, 그리고 $(1,2,2)$ 과 $(2,1,3)$ 또는 $(1,2,3)$ 과 $(2,1,2)$ 또 다른 두 가지 솔루션.
사례 2 : $(2,3,7)$
숫자들 $5$ 과 $6$주 대각선 (오른쪽 상단, 중간 정사각형, 왼쪽 하단)의 세 지점 중 두 지점에 있어야합니다. 따라서$3!=6$할당 방법. 둘 다 중간 공간에 있지 않은 두 경우$4$ 중간 공간에 있어야하며 숫자에 대해 두 가지 가능한 배열이 있습니다. $2$ 과 $3$. 나머지 4 개의 경우에는 각각 숫자가$4$주 대각선의 나머지 공간과 그렇지 않은 공간에 있습니다. 결과적으로 다음과 같은 경우 총 16 개의 준비가 이루어집니다.$(2,3,7)$.
따라서 총 약정 수는 $2(3+2+2\cdot2+4\cdot3)=42$
그만큼 $1$ 그리고 $9$왼쪽 상단과 오른쪽 하단 모서리에 각각 명확하게 들어가야합니다. 확인하기 쉽습니다.$5$ 둘 중 하나에 인접 할 수 없습니다 $1$ 아니면 그 $9$, 따라서 "안티"대각선의 세 지점 중 하나에 있어야합니다. 약간의 표기법을 발명하여 가능성의 수를 다음과 같이 쓸 수 있습니다.
$$\#\pmatrix{1&*&\\*&5&-\\&-&9}+2\times\#\pmatrix{1&*&5\\*&&-\\&-&9}$$
어디 "$\#$"의 $3\times3$ 배열은 솔루션의 수를 나타냅니다. $1$, $5$, 및 $9$ 지정된 장소에서 각각 $*$ 사이의 숫자로 이해 $1$ 과 $5$ 그리고 각각 $-$ 사이의 숫자 $5$ 과 $9$. "$2\times\,$"는 대칭을위한 것입니다. $5$왼쪽 하단 모서리에 있습니다. 같은 대칭으로 우리는
$$\#\pmatrix{1&*&\\*&5&-\\&-&9}=2\times\#\pmatrix{1&*&*\\*&5&-\\-&-&9}$$
이제 세 가지가 $*$의 숫자로 채울 수 있습니다. $2$, $3$, 및 $4$ 그냥 $3$ 다른 방법으로, 마찬가지로 세 가지 $-$숫자와 함께 $6$, $7$, 및 $8$, 그래서
$$\#\pmatrix{1&*&\\*&5&-\\&-&9}=2\times3\times3$$
다소 다른 대칭 주장은 우리에게
$$\#\pmatrix{1&*&5\\*&&-\\&-&9}=2\times\#\pmatrix{1&*&5\\*&*&-\\-&-&9}$$
이 경우 이제 $4$ 들어갈 수있는 지점이 하나뿐입니다.
$$\#\pmatrix{1&*&5\\*&*&-\\-&-&9}=\#\pmatrix{1&*&5\\*&4&-\\-&-&9}=2\times3$$
모든 것을 합치면 총 준비 수는
$$(2\times3\times3)+(2\times2\times\times2\times3)=18+24=42$$
비고 (나중에 추가됨) : 명확성과 정확성을 위해 "다소 다른"대칭이
$$\#\pmatrix{1&*&5\\*&*&-\\-&-&9}=\#\pmatrix{1&*&5\\*&-&-\\*&-&9}$$
숫자 대체가 뒤 따르는 (또는 선행 된) "안티"대각선을 가로 지르는 반사입니다. $k\to10-k$ 각각 $k\in\{1,2,3,4,5,6,7,8,9\}$.