El máximo número de diferentes diagonales obtenidos por la columna de permutaciones

Question

Considere la posibilidad de un n x n matriz con entradas de ser sólo un '0' y '1'.

Por ejemplo: $\left( \begin{array}{ccc} 1 & 0 & 1\\1 & 1 & 0\\0&0&1\end{array}\right)$

Podemos entonces considerar a todos los de la columna de permutaciones de la matriz, y el recuento de los diferentes tipos de diagonales a partir de la parte inferior izquierda a la esquina superior derecha:

Número 1) $\left( \begin{array}{ccc} 1 & 0 & 1\\1 & 1 & 0\\0&0&1\end{array}\right)$ Diagonal: 011

Número 2)$\left( \begin{array}{ccc} 1 & 1 & 0\\1 & 0 & 1\\0&1&0\end{array}\right)$ Diagonal: 000

Número 3)$\left( \begin{array}{ccc} 0 & 1 & 1\\1 & 1 & 0\\0&0&1\end{array}\right)$ Diagonal: 011

Número 4)$\left( \begin{array}{ccc} 0 & 1 & 1\\1 & 0 & 1\\0&1&0\end{array}\right)$Diagonal: 001

El Número 5)$\left( \begin{array}{ccc} 1 & 1 & 0\\0 & 1 & 1\\1&0&0\end{array}\right)$ Diagonal: 110

Número 6)$\left( \begin{array}{ccc} 1 & 0 & 1\\0 & 1 & 1\\1&0&0\end{array}\right)$ Diagonal: 111

Hay un total de 5 diferentes posibles diagonales: 011, 000, 001, 110, 111.

La pregunta es, dada cualquier matriz con entradas de ser '0' y '1', ¿cuál es el número máximo de posibles diagonales? He probado algunas de las conjeturas y parece que la fórmula de máxima diagonales que parecen ser $2^n-n$. Por ejemplo,$2^3-3=5$.

Gracias por la ayuda en la búsqueda de la fórmula general para el máximo número de diagonales, entre todos los n x n matrices (fija de n, entre todas las matrices)!

• La matriz puede ser cualquier n x n matriz, siempre y cuando se obtiene el máximo número de diferentes diagonales con respecto a la columna de permutaciones.

Answer 1

Si tenemos en cuenta la diagonal principal, que el máximo número no va a cambiar, y que podemos traducir el problema (considerando la diagonal principal) de la siguiente manera:

Deje $A=[A_{ij}]$ ser un $n\times n$ $(0,1)$-de la matriz. Deje $S_n$ grupo simétrico de orden $n$ (conjunto de todas las permutaciones de $\{1,2,\dots,n\}$). Si $\mathcal{P}(A)=\{(A_{1\alpha(1)}, A_{2\alpha(2)},\dots,A_{n\alpha(n)})\ |\ \ \ \ \alpha\in S_n\}$, muestran que $$|\mathcal{P}(A)|\le 2^n-n.$$

No estoy seguro de cómo probar que para cualquier $(0,1)$-matriz, pero no es tan difícil mostrar que $|\mathcal{P}(I_n)|= 2^n-n.$ . He aquí cómo:

Primero, note que cualquier elemento de a $\mathcal{P}(A)$ es un binario de longitud $n$, debido a $A$ $(0,1)$- matriz. Por lo $|\mathcal{P}(A)|\le 2^n$ cualquier $(0,1)$-matriz $A$. Pero para la identidad de la matriz binaria con exactamente un $0$ no pudo ser en $\mathcal{P}(I_n)$, de lo contrario tenemos una fila cero que no es posible. Dado que el número de archivos binarios con exactamente un $0$$n$, por lo que tenemos $|\mathcal{P}(I_n)|\le 2^n-n$. Pero cualquier otro binario es pasar a ser en $\mathcal{P}(I_n)$ porque, por ejemplo, si $(x_1,x_2,\dots,x_n)$ es un binario con $x_{i_1}=x_{i_2}=\cdots=x_{i_m}=0$, $2\le m$, y en otros lugares de $1$, a continuación, mediante la permutación $\alpha=(i_1 i_2\dots i_t)$ vemos que $(x_1,x_2,\dots,x_n)=(\delta_{1\alpha(1)}, \delta_{2\alpha(2)},\dots,\delta_{n\alpha(n)})\in\mathcal{P}(I_n)$, así como reclamamos $|\mathcal{P}(I_n)|= 2^n-n.$

---

Si hay cualquier problema con esta solución por favor, escriba un comentario y que me haga saber.