Número de $n^2\times n^2$ permutación de matrices con un 1 en cada una de las $n\times n$ subgrid

Question

He encontrado la siguiente pregunta en un papel que estaba tratando de resolver:

La siguiente figura muestra un $3^2 \times 3^2$ cuadrícula dividida en $3^2$ subgrids de tamaño $3 \times 3$. Esta red ha $81$ células, $9$ en cada subgrid.

Ahora considere un $n^2 \times n^2$ cuadrícula dividida en $n^2$ subgrids de tamaño $n \times n$. Hallar el número de maneras en que usted puede seleccionar $n^2$ células de esta red que no es exactamente una célula proveniente de cada subgrid, uno de cada fila y uno de cada columna.

Yo:

Ya tenemos $n^2$ filas $n^2$ columnas y $n^2$ subgrids en total, tenemos que elegir una y sólo una célula de cada uno de ellos. Vamos a elegir una en una. Podemos elegir la primera celda en $n^4$ muchas maneras. Entonces, tendremos que evitar que subgrid, la columna y la fila que hemos elegido la primera de ellas a partir de la hora de elegir la segunda celda. Por lo tanto, tenemos $n^4-n^2-2n(n-1)$ opciones. Podemos continuar este para obtener el número total de formas posibles. Pero, creo que hay un agujero. Decir, hemos elegido la primera celda de la subgrid de la esquina izquierda y la segunda a partir de la subgrid apenas a la derecha, por lo que no viola ninguna de las reglas. Luego, a la hora de encontrar el número de maneras en las que podemos elegir la tercera celda, tendríamos que restar algunas de las células dos veces. Creo que usted lo consigue. Por favor, si alguien me puede ayudar a resolver este problema, sería muy apreciado.

Answer 1

Así, en un $2^2 \times 2^2$ cuadrícula existen 4 opciones para la parte superior izquierda de sub rejilla, entonces como representante de la parte superior derecha subgrid no puede estar en la misma fila, hay 2 opciones. Como la parte inferior izquierda de la rep no puede estar en la misma columna como el representante de la parte superior hay 2 opciones. Sólo hay una opción a la izquierda de la parte inferior derecha de sub red.

En total hay 4*2*2*1 = 16 opciones. O $[2*2][(2 - 1)2]\times[2*(2-1)][(2-1)(2-1)]$ o, en general,$\prod_{i=1}^n\prod_{k=1}^n ik$.

Este es el mismo argrument en la fila superior de la sub cuadrículas no $n^2$ opciones para el primer subgrid. $(n-1)n$ para el segundo y así sucesivamente. Esto es $\prod_{k=1}^n n*k$. Para el segundo de la fila superior (n-1 de la parte inferior) de subgrids hay $n(n-1)$ opciones para el primer subgrid, $(n-1)(n -1)$ para el segundo y así sucesivamente. Esto es $\prod_{k=1}^n (n-1)k$. Para todos los lth fila de sub cuadrículas hay $n(n-l)$ opciones para el primer subgrid, $(n -1)(n -l)$ para el segundo y así sucesivamente. Esto es $\prod_{k=1}^n (n -l)k$. El total de los productos para todas las filas de subgrids es $\prod_{i=1}^n\prod_{k=1}^n ik$.

====

Hmmm, cuando lo he publicado yo en realidad debería haber continuado:

$\prod_{i=1}^n(\prod_{k=1}^n ik)=$

$\prod_{i=1}^n(i^n n!)=$

$(n!)^n (n!^n) = n!^{2n}$

Así que para un $2^2 \times 2^2$ red es $(2!)^{2*2} = 2^4 =16$.

Para el $3^2 \times 3^2$ red es $3!^{2*3} = 6^6 = 46,656$.

(Que me imagino que debe ser $(9*6*3)*(6*4*2)*(3*2*1) = (3^4*2)(3*2^4)(3*2) = 3^6*2^6 = 6^6$. Sí, parece encajar.)

Me imagino 16 x 16 va a ser un monstruo! $(4!)^{2*4} = 24^8 = 110,075,314,176.$ Wow!

Por un lado es $(16*12*8*4)(12*9*6*3)(8*6*4*2)(4*3*2*1)=(4^4*4!)(3^4*4!)(2^4*4!)(4!) = (4!)^4(4!)^4 = 4!^{2*4}$ que.. sí...

Answer 2

Utilizando el sistema de conteo descritos en los comentarios, podemos asociar a cada subgrid un entero positivo: el número de decisiones en que subgrid. Es bastante claro que el número es invariante del método exacto de llegar a ese subgrid: sin embargo, usted hacerlo, subgrid $(i,j)$ (en la costumbre de la matriz sufijo notation) se ha asociado con es $(n+1-i)(n+1-j)$ opciones. Ahora que las matrices que se van como sigue: \begin{eqnarray*} n=1 &\mapsto& \begin{pmatrix}1\end{pmatrix}\\ n=2 &\mapsto& \begin{pmatrix}4&2\\2&1\end{pmatrix}\\ n=3 &\mapsto& \begin{pmatrix}9&6&3\\6&4&2\\3&2&1\end{pmatrix}\\ &\vdots&\\ n=k&\mapsto& \begin{pmatrix} k^{2} & k(k-1) & k(k-2) & \ldots & 2k & k\\ k(k-1) & (k-1)^{2} & (k-1)(k-2) & \ldots & 2(k-1) & k-1\\ k(k-2) & (k-1)(k-2) & (k-2)^{2} & \ldots & 2(k-2) & k-2\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 2k & 2(k-1) & 2(k-2) & \ldots & 4 & 2\\ k & k-1 & k-2 & \ldots & 2 & 1 \end{pmatrix}\\ &\vdots& \end{eqnarray*} Para cada una de las $n$, la respuesta al problema es el producto de todas las entradas de la matriz correspondiente; indicar cada uno de estos números por $P_{n}$. Ahora ya cada matriz contiene la anterior matriz como un "submatriz", es evidente que podemos encontrar una fórmula recursiva: en particular, algunos pensaron que da \begin{eqnarray*} P_{n} & = & P_{n-1}n^{2}\prod_{i=1}^{n-1}(in)^{2}\\ & = & P_{n-1}n^{2n}[(n-1)!]^{2}, \end{eqnarray*} con la condición inicial $P_{1}=1$.

Ahora, para cada una de las $n\in\mathbb{N}$ deje $f(n) = (n!)^{2n}$. Claramente $P_{1}=f(1)$. Además, supongamos que, para algunos,$n\in\mathbb{N}$, sabemos que $P_{n-1} = f(n-1)$; luego tenemos \begin{eqnarray*} P_{n} & = & P_{n-1}n^{2n}[(n-1)!]^{2}\\ & = & [(n-1)!]^{2(n-1)}n^{2n}[(n-1)!]^{2}\\ & = & (n!)^{2n}\\ & = & f(n). \end{eqnarray*}

Por inducción, $P_{n} = (n!)^{2n}$ todos los $n\in\mathbb{N}$.

Answer 3

Creo que he encontrado una solución. Así como @WillR sugerido, que me mostró el enfoque correcto, voy a postear esto como una respuesta. Por favor, siéntase libre de notificarme acerca de las fallas de lógica, si los hay. Así que, aquí va:

Vamos a empezar por la elección de una celda de la parte superior izquierda subgrid. Como tenemos que seleccionar las celdas de cada subgrids, no creo que este enfoque podría afectar el resultado final. Tenemos $n^2$ opciones en la elección de la primera celda, a continuación,. Ahora, nos movemos hacia la derecha subgrid. Esta vez, tendremos que tener en cuenta que una de las filas se utiliza. Por lo tanto, tenemos $n(n-1)$ opciones de la izquierda. Si seguimos de esta manera, el número total de maneras en la que podemos seleccionar $n$ celdas de la fila superior es $$n^2 \cdot n(n-1) \cdot \cdot \cdot n=n^n \cdot n!$$ Ahora, pasemos a la segunda fila de la parte superior. Ahora, que no tiene que preocuparse acerca de la utiliza filas más, sólo la utilizan columnas. Así, cuando la elección de la primera a partir de aquí, tenemos $n(n-1)$ opciones. Cuando nos trasladamos a la segunda subgrid, tendremos que evitar una fila, pero que reduce el número de opciones por $(n-1)$, no $n$. Porque, la fila y la columna tenemos que evitar que se tiene un celular común. Continuando de esta manera, en el caso de la segunda fila, tenemos un total de $(n-1)^n \cdot n!$ opciones.

Continuando de esta manera, el número de opciones para el $r$'th fila sería $(n-r+1)^n \cdot n!$. Como las opciones son independientes, podemos multiplicar para obtener el número total de opciones. Que sería: $$\prod_{r=1}{n!^n \cdot (n-r+1)^n} = n!^n \cdot \prod_{r=1}^nr^n=n!^n \cdot n!^n ={n!}^{2n}$$