Combien $3\times 3$ tableaux avec des chiffres de $1$ à $9$ avec l'ordre croissant y a-t-il?
Les entrées dans un $3 \times 3$ tableau comprend tous les chiffres de $1$ à travers $9$, disposés de manière à ce que les entrées de chaque ligne et colonne soient dans l'ordre croissant. Combien y a-t-il de tableaux de ce type?
C'est une question sur la combinatoire. J'ai essayé d'utiliser des tableaux et des numéros de crochet, mais je n'ai pas compris après cela, veuillez dire comment résoudre ce problème. Ce serait plus facile pour moi s'il était résolu en utilisant la combinatoire normale. Mais pas de restrictions. C'est ton choix
Réponses
Utiliser la notation $(A,B,C)$ pour décrire le nombre $C$ étant situé dans le $A$ rangée et $B$colonne. En raison de la symétrie, la transposée (réflexion sur la diagonale principale) de toute solution est une solution différente, en d'autres termes, si nous avons une solution:$$\{(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)\}$$ alors nous avons aussi une solution: $$\{(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)\}$$
Parce que chaque ligne et colonne doit être dans un ordre croissant, nous savons que notre solution doit inclure $(1,1,1)$ et $(3,3,9)$.
Nous avons deux choix pour savoir où mettre le numéro $8$. En raison de la symétrie, nous ne considérerons que les solutions avec$(3,2,8)$, et devra simplement doubler le nombre de solutions.
Nous avons maintenant deux choix pour savoir où mettre $7$:
Cas 1: $(3,1,7)$
Le nombre $6$ est verrouillé comme $(2,3,6)$. Le nombre$5$ peut être soit dans $(2,2,5)$ ou $(1,3,5)$. Si$(2,2,5)$, puis les chiffres $2,3,4$doivent être dans les trois emplacements restants; dès que nous choisissons celui qui se trouve$(2,1,X)$, puis les autres sont verrouillés en place, donnant trois solutions avec $(3,1,7)$ et $(2,2,5)$. Si$(1,3,5)$, alors nous devons avoir $(2,2,4)$, et n'ont que soit $(1,2,2)$ et $(2,1,3)$ ou $(1,2,3)$ et $(2,1,2)$ pour deux autres solutions.
Cas 2: $(2,3,7)$
Les nombres $5$ et $6$doit être dans deux des trois points de l'antidiagonal principal (le haut à droite, le carré du milieu et le bas à gauche). Le sont donc$3!=6$les moyens de les attribuer. Dans les deux cas où ni l'un ni l'autre n'est dans l'espace du milieu, le nombre$4$ doit être dans l'espace du milieu, et il y a deux arrangements possibles pour les nombres $2$ et $3$. Dans chacun des quatre autres cas, il y a deux cas où le nombre$4$est dans l'espace restant sur l'antidiagonal principal et celui où il ne l'est pas. Il en résulte un total de 16 arrangements si$(2,3,7)$.
Par conséquent, le nombre total d'arrangements est $2(3+2+2\cdot2+4\cdot3)=42$
le $1$ et le $9$doit clairement aller dans les coins supérieur gauche et inférieur droit, respectivement. Il est facile de voir que le$5$ ne peut être adjacent ni au $1$ ou la $9$, par conséquent, il doit aller dans l'un des trois endroits de la diagonale "anti". En inventant un peu de notation, on peut écrire le nombre de possibilités comme
$$\#\pmatrix{1&*&\\*&5&-\\&-&9}+2\times\#\pmatrix{1&*&5\\*&&-\\&-&9}$$
où le "$\#$"d'un $3\times3$ tableau indique le nombre de solutions avec $1$, $5$, et $9$ aux emplacements assignés, avec chacun $*$ compris comme un nombre entre $1$ et $5$ et chacun $-$ un nombre entre $5$ et $9$. Le "$2\times\,$"est pour la symétrie qui aurait le $5$dans le coin inférieur gauche. Par la même symétrie, nous avons
$$\#\pmatrix{1&*&\\*&5&-\\&-&9}=2\times\#\pmatrix{1&*&*\\*&5&-\\-&-&9}$$
et il est maintenant facile de voir que les trois $*$'s peut être rempli avec les nombres $2$, $3$, et $4$ en juste $3$ différentes manières, et de même pour les trois $-$c'est avec les chiffres $6$, $7$, et $8$, pour que
$$\#\pmatrix{1&*&\\*&5&-\\&-&9}=2\times3\times3$$
Un argument de symétrie quelque peu différent nous dit
$$\#\pmatrix{1&*&5\\*&&-\\&-&9}=2\times\#\pmatrix{1&*&5\\*&*&-\\-&-&9}$$
et dans ce cas maintenant le $4$ n'a qu'un seul endroit où il peut entrer:
$$\#\pmatrix{1&*&5\\*&*&-\\-&-&9}=\#\pmatrix{1&*&5\\*&4&-\\-&-&9}=2\times3$$
En mettant tout ensemble, le nombre total d'arrangements est
$$(2\times3\times3)+(2\times2\times\times2\times3)=18+24=42$$
Remarque (ajoutée plus tard): Pour plus de clarté et de précision, la symétrie «quelque peu différente» qui nous dit
$$\#\pmatrix{1&*&5\\*&*&-\\-&-&9}=\#\pmatrix{1&*&5\\*&-&-\\*&-&9}$$
est une réflexion à travers la diagonale "anti" suivie (ou précédée) du remplacement numérique $k\to10-k$ pour chaque $k\in\{1,2,3,4,5,6,7,8,9\}$.