Quanti $3\times 3$ matrici con cifre da $1$ per $9$ con ordine crescente ci sono?

Aug 16 2020

Le voci in a $3 \times 3$ array include tutte le cifre da $1$ attraverso $9$, disposto in modo che le voci in ogni riga e colonna siano in ordine crescente. Quanti di questi array ci sono?

Questa è una domanda sulla combinatoria. Ho provato a usare i tableaus e ad usare i numeri di hook ma non sono riuscito a capire dopo, per favore dimmi come risolverlo. Sarebbe più facile per me se risolto usando la normale combinatoria. Ma nessuna restrizione. È la vostra scelta

Risposte

1 Moko19 Aug 16 2020 at 22:15

Usando la notazione $(A,B,C)$ per descrivere il numero $C$ essendo situato nel $A$ riga e $B$colonna. A causa della simmetria, la trasposizione (riflessione sulla diagonale principale) di qualsiasi soluzione è una soluzione diversa, in altre parole, se abbiamo una soluzione:$$\{(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)\}$$ allora abbiamo anche una soluzione: $$\{(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)\}$$

Poiché ogni riga e colonna deve essere in ordine crescente, sappiamo che la nostra soluzione deve includere $(1,1,1)$ e $(3,3,9)$.

Abbiamo due scelte per dove mettere il numero $8$. A causa della simmetria, considereremo solo le soluzioni con$(3,2,8)$e dovrà solo raddoppiare il numero di soluzioni.

Ora abbiamo due scelte per dove mettere $7$:

Caso 1: $(3,1,7)$

Il numero $6$ è bloccato come $(2,3,6)$. Il numero$5$ può essere in $(2,2,5)$ o $(1,3,5)$. Se$(2,2,5)$, poi i numeri $2,3,4$essere nei tre posti rimanenti; non appena scegliamo in quale si trova$(2,1,X)$, quindi gli altri vengono bloccati, fornendo tre soluzioni con $(3,1,7)$ e $(2,2,5)$. Se$(1,3,5)$, quindi dobbiamo avere $(2,2,4)$e hanno solo entrambi $(1,2,2)$ e $(2,1,3)$ o $(1,2,3)$ e $(2,1,2)$ per altre due soluzioni.

Caso 2: $(2,3,7)$

I numeri $5$ e $6$deve essere in due dei tre punti dell'antidiagonale principale (in alto a destra, nel quadrato centrale e in basso a sinistra). Lo sono quindi$3!=6$modi di assegnarli. Nei due casi in cui nessuno dei due è nello spazio centrale, il numero$4$ deve essere nello spazio centrale e ci sono due possibili disposizioni per i numeri $2$ e $3$. In ciascuno degli altri quattro casi, ci sono due casi in cui il numero$4$è nello spazio rimanente sull'antidiagonale principale e uno dove non lo è. Il risultato è un totale di 16 arrangiamenti se$(2,3,7)$.

Pertanto, il numero totale di accordi è $2(3+2+2\cdot2+4\cdot3)=42$

1 BarryCipra Aug 31 2020 at 16:36

Il $1$ e il $9$deve chiaramente andare negli angoli in alto a sinistra e in basso a destra, rispettivamente. È facile vedere che il file$5$ non può essere adiacente a $1$ o il $9$, quindi deve andare in uno dei tre punti della diagonale "anti". Inventando un po 'di notazione, possiamo scrivere il numero di possibilità come

$$\#\pmatrix{1&*&\\*&5&-\\&-&9}+2\times\#\pmatrix{1&*&5\\*&&-\\&-&9}$$

dove il "$\#$" di una $3\times3$ array indica il numero di soluzioni con $1$, $5$, e $9$ in punti assegnati, con ciascuno $*$ inteso come un numero tra $1$ e $5$ e ciascuno $-$ un numero compreso tra $5$ e $9$. Il "$2\times\,$"è per la simmetria che avrebbe il $5$nell'angolo inferiore sinistro. Con la stessa simmetria, abbiamo

$$\#\pmatrix{1&*&\\*&5&-\\&-&9}=2\times\#\pmatrix{1&*&*\\*&5&-\\-&-&9}$$

ed è ora facile vedere che i tre $*$Può essere riempito con i numeri $2$, $3$, e $4$ in appena $3$ modi diversi, e lo stesso per i tre $-$E 'con i numeri $6$, $7$, e $8$, così che