Dados m y n, tenemos que averiguar el número de posibles matrices de orden m*n con la propiedad de que A(i,j) puede ser 0 o 1 y que ninguna submatriz contigua de longitud > 1 y anchura > 1 debe tener las mismas entradas, es decir, todas sus celdas no deben ser 0 o 1. Por ejemplo, si m = 2 y n = 2, la respuesta es 14: Posibilidades totales : 2 ^ (2 * 2); Casos no válidos: cuando las 4 celdas son 0 ó 1. Por lo tanto, la respuesta es 2 ^ (2 * 2) - 2 = 14. Es válida una submatriz de longitud > 1 y anchura = 1, también de anchura > 1 y longitud = 1.
Respuestas
¿Demasiados anuncios?
Dejemos que $a_n$ sea el número de $2 \times n$ -evitando las submatrices constantes de 2*2. Entonces
$$a_n = \frac{2^{-n} \left(4 \left(17+4 \sqrt{17}\right) \left(3+\sqrt{17}\right)^n+\left(\sqrt{17}-17\right) \left(\sqrt{17}-3\right)^n e^{i \pi n}\right)}{17 \left(3+\sqrt{17}\right)}$$
Esto debería ser bastante sencillo de demostrar, dejemos que $v(n)=(e_{01}(n),e_{10}(n),e_{00}(n),e_{11}(n))$ sea el vector del número de $2\times n$ -matrices que terminan en la columna 01, 10, 00 resp. 11.
Tenemos entonces la recursión $$v(n+1)=\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \end{pmatrix} v(n)$$
Como esto es simétrico, podemos diagonalizarlo y a partir de aquí, debería ser sencillo encontrar la fórmula anterior. (He hecho un poco de trampa en Mathematica).
EDIT: Por supuesto, $e_{01}(n)=e_{10}(n)$ y $e_{00}(n)=e_{11}(n)$ por simetría, por lo que, por supuesto, se puede reducir lo anterior a una recursión de la matriz de 2 por 2, con entradas 2,2 y 2,1. Los valores propios de esta matriz son $1/2 (3 + \sqrt{17}), 1/2 (3 - \sqrt{17})$ lo que explica la extraña fórmula anterior.
asonnenschein
Puntos
476
EDITAR : He editado el argumento para hacerlo más sólido Supongamos que $m\geq 3$ y $n\geq 5$ para que haya una submatriz A de 3x5. Demuestro que el número de posibilidades es cero en este caso.
En A, hay al menos dos filas con al menos allí $1$ cada uno (hasta el reetiquetado de los símbolos). Como no podemos tener una submatriz constante de 2x2, podemos suponer que las dos primeras filas de la matriz son [11100] y [00111].
Para evitar una submatriz contante de 2x2, las dos primeras entradas de la tercera fila deben ser diferentes, pero entonces, sea cual sea la elección que hagamos para la tercera, obtendremos una submatriz constante de 2x2 en la primera y tercera fila.
La respuesta para $m=1$ y $m=2$ no es difícil de calcular explícitamente.
Junto con la respuesta anterior, esto reduce el problema a la comprobación de los siguientes casos (que no es demasiado difícil): 3x3,3x4,4x4.
