Número de matrices cuadradas binarias cuya submatriz contigua de 2 por 2 tiene exactamente 2 unos (ceros)

Question

¿Cuál es el número de binarios $n\times n$ cuyas matrices contiguas $2\times 2$ submatriz tiene exactamente dos unos (ceros)?

Es decir, si $a_{ij}\in\{0,1\}$ para $i,j\in\{1,2,\dots,n\}$ son entradas de la matriz, entonces $$a_{i,j} + a_{i,j+1} + a_{i+1,j} + a_{i+1,j+1}= 2$$

para $i \in \{1,\dots,n-1\}$ y $j \in \{1,\dots,n-1\}$ donde $n\ge 2$ .

Después de escribir algunos casos para pequeños $n$ me parece que la respuesta podría ser $2^{n+1}-2$ .

¿Hay alguna forma elegante de demostrarlo?

---

Por ejemplo, para $n=2$ tenemos $6$ matrices

$$ \begin{bmatrix} 1 &0 \\ 1 &0 \\ \end{bmatrix}, \begin{bmatrix} 1 &1 \\ 0 &0 \\ \end{bmatrix}, \begin{bmatrix} 1 &0 \\ 0 &1 \\ \end{bmatrix}, \begin{bmatrix} 0 &1 \\ 1 &0 \\ \end{bmatrix}, \begin{bmatrix} 0 &0 \\ 1 &1 \\ \end{bmatrix}, \begin{bmatrix} 0 &1 \\ 0 &1 \\ \end{bmatrix}. $$

Por ejemplo, para $n=3$ tenemos $14$ matrices:

1. $4$ rotaciones de $\begin{bmatrix} 1 &0 &1 \\ 1 &0 &1 \\ 0 &1 &0 \\ \end{bmatrix}$ , $2$ rotaciones de $\begin{bmatrix} 1 &0 &1 \\ 1 &0 &1 \\ 1 &0 &1 \\ \end{bmatrix}$ , $1$ matriz $\begin{bmatrix} 1 &0 &1 \\ 0 &1 &0 \\ 1 &0 &1 \\ \end{bmatrix}$ .
2. Uno adicional $(J-M)$ para cada una de $7$ matrices $M$ del caso anterior.

$J$ es una matriz llena de $1$ en cada entrada.

Answer 1

Trabajaremos en los números de la primera fila del $n*n$ mesa en dos casos:

1. La primera fila es $1,0,1,0,\dotsb$ o $0,1,0,1,\dotsb$
2. Hay dos elementos consecutivos en el primer conjunto. En primer lugar, está claro que en el primer caso la respuesta es exactamente $2^n$ :
   Denomina fila simple a toda fila sin elementos consecutivos. Ahora bien, si se da el primer caso, cada fila puede ser una fila simple y son todos los casos sin elementos consecutivos en la primera fila por lo que, el primer caso es de $2^n$ casos.
   Por otro lado, en el segundo caso demostraremos que el resto de la tabla se puede construir de forma única:
   Los dos cuadrados unitarios bajo los dos elementos consecutivos de la primera fila se eligen unívocamente y, a partir de estos dos, se construye unívocamente el resto de la segunda fila. Del mismo modo, la segunda fila tiene al menos dos elementos consecutivos (los dos cuadrados unitarios bajo los dos elementos consecutivos de la primera fila son iguales), por lo que la tercera fila se construye de forma única, y así sucesivamente. Por tanto, en el segundo caso, el resto de la tabla se construye de forma única. Así que el número de casos de las tablas del segundo tipo es igual al número de conjuntos binarios excepto los dos conjuntos simples que es $2^n-2$ por lo que la respuesta es igual a $2^n+2^n-2=2^{n+1}-2$

Answer 2

La primera fila puede ser cualquiera de los $2^n$ miembros de $\{0,1\}^n$ . Dada la $k$ 'th row $(x_1, \ldots, x_n)$ El $k+1$ 'th fila siempre se puede $(1-x_1, \ldots, 1-x_n)$ . La única otra posibilidad es que el $k+1$ La fila es $(x_1,\ldots, x_n)$ pero sólo si el $k$ 'th fila se alterna $(0,1,0,1,\ldots)$ o $(1,0,1,0,\ldots)$ . Ahora usa la inducción sobre el número de filas...