Ile $3\times 3$ tablice z cyframi od $1$ do $9$ z rosnącym porządkiem są tam?
Wpisy w $3 \times 3$ tablica zawiera wszystkie cyfry z $1$ przez $9$, ułożone w taki sposób, że wpisy w każdym wierszu i kolumnie są uporządkowane rosnąco. Ile jest takich tablic?
To jest pytanie dotyczące kombinatoryki. Próbowałem użyć tableaus i numerów haków, ale po tym nie mogłem zrozumieć, proszę, powiedz, jak rozwiązać ten problem. Byłoby dla mnie łatwiejsze, gdyby zostało rozwiązane za pomocą zwykłej kombinatoryki. Ale bez ograniczeń. To Twój wybór
Odpowiedzi
Korzystanie z notacji $(A,B,C)$ opisać liczbę $C$ znajduje się w $A$ wiersz i $B$kolumna. Ze względu na symetrię transpozycja (odbicie w poprzek głównej przekątnej) dowolnego rozwiązania jest innym rozwiązaniem, innymi słowy, jeśli mamy rozwiązanie:$$\{(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)\}$$ wtedy też mamy rozwiązanie: $$\{(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)\}$$
Ponieważ każdy wiersz i kolumna muszą być uporządkowane rosnąco, wiemy, że nasze rozwiązanie musi uwzględniać $(1,1,1)$ i $(3,3,9)$.
Mamy dwie możliwości, gdzie umieścić tę liczbę $8$. Ze względu na symetrię rozważymy tylko rozwiązania z$(3,2,8)$, i wystarczy podwoić liczbę rozwiązań.
Mamy teraz dwie możliwości, gdzie umieścić $7$:
Przypadek 1: $(3,1,7)$
Numer $6$ jest zablokowany jako $(2,3,6)$. Numer$5$ może być w $(2,2,5)$ lub $(1,3,5)$. Gdyby$(2,2,5)$, potem liczby $2,3,4$muszą znajdować się w trzech pozostałych miejscach; gdy tylko wybierzemy, który jest w środku$(2,1,X)$, to reszta jest zablokowana na miejscu, dając trzy rozwiązania z $(3,1,7)$ i $(2,2,5)$. Gdyby$(1,3,5)$, to musimy mieć $(2,2,4)$i masz tylko jedno lub drugie $(1,2,2)$ i $(2,1,3)$ lub $(1,2,3)$ i $(2,1,2)$ za kolejne dwa rozwiązania.
Przypadek 2: $(2,3,7)$
Liczby $5$ i $6$musi znajdować się w dwóch z trzech punktów głównego antidiagonalnego (w prawym górnym rogu, środkowym kwadracie i lewym dolnym rogu). Dlatego są$3!=6$sposoby ich przypisywania. W dwóch przypadkach, w których żadna z nich nie znajduje się w środkowej przestrzeni, liczba$4$ musi znajdować się w środkowej przestrzeni, a liczby są możliwe na dwa sposoby $2$ i $3$. W każdym z pozostałych czterech przypadków są dwa przypadki, w których liczba$4$znajduje się na pozostałej przestrzeni na głównej antidiagonalnej i takiej, w której jej nie ma. To daje w sumie 16 aranżacji, jeśli$(2,3,7)$.
W związku z tym całkowita liczba ustaleń wynosi $2(3+2+2\cdot2+4\cdot3)=42$
Plik $1$ i $9$muszą wyraźnie iść odpowiednio w lewym górnym i prawym dolnym rogu. Łatwo zauważyć, że$5$ nie może sąsiadować z $1$ albo $9$, dlatego musi iść w jednym z trzech miejsc na przekątnej „anty”. Wymyślając trochę notacji, możemy zapisać liczbę możliwości jako
$$\#\pmatrix{1&*&\\*&5&-\\&-&9}+2\times\#\pmatrix{1&*&5\\*&&-\\&-&9}$$
gdzie "$\#$"z a $3\times3$ tablica oznacza liczbę rozwiązań z $1$, $5$, i $9$ w wyznaczonych miejscach, z każdym $*$ rozumiana jako liczba pomiędzy $1$ i $5$ i każdy $-$ liczba pomiędzy $5$ i $9$. „$2\times\,$„jest dla symetrii, która miałaby rozszerzenie $5$w lewym dolnym rogu. Mamy taką samą symetrię
$$\#\pmatrix{1&*&\\*&5&-\\&-&9}=2\times\#\pmatrix{1&*&*\\*&5&-\\-&-&9}$$
i teraz łatwo zauważyć, że te trzy $*$można wypełnić liczbami $2$, $3$, i $4$ po prostu $3$ na różne sposoby i podobnie dla wszystkich trzech $-$jest z liczbami $6$, $7$, i $8$więc to
$$\#\pmatrix{1&*&\\*&5&-\\&-&9}=2\times3\times3$$
Mówi nam nieco inny argument symetrii
$$\#\pmatrix{1&*&5\\*&&-\\&-&9}=2\times\#\pmatrix{1&*&5\\*&*&-\\-&-&9}$$
iw tym przypadku teraz $4$ ma tylko jedno miejsce, do którego może wejść:
$$\#\pmatrix{1&*&5\\*&*&-\\-&-&9}=\#\pmatrix{1&*&5\\*&4&-\\-&-&9}=2\times3$$
Łącząc wszystko razem, całkowita liczba aranżacji to
$$(2\times3\times3)+(2\times2\times\times2\times3)=18+24=42$$
Uwaga (dodana później): Dla jasności i precyzji, mówi nam „nieco inna” symetria
$$\#\pmatrix{1&*&5\\*&*&-\\-&-&9}=\#\pmatrix{1&*&5\\*&-&-\\*&-&9}$$
jest odbiciem w poprzek przekątnej „anty”, po której następuje (lub poprzedza) zamiana numeryczna $k\to10-k$ dla każdego $k\in\{1,2,3,4,5,6,7,8,9\}$.