Puentes a través de un suelo de baldosas

Question

Un par de años atrás, un amigo mío hizo un seminario sobre "Puentes a través de un suelo de baldosas". Un "puente" se define como una fila o columna de una $n \times n$ de la matriz binaria compuesta totalmente de $1$'s, por ejemplo en la tercera columna y la fila cuarta de

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

El problema es hallar la probabilidad de selección de una $n\times n$ de la matriz binaria con al menos un puente, cuando la selección de todos los $n\times n$ matrices binarias. Mi amigo hizo un algoritmo utilizando cadenas de Markov para el cálculo para un determinado $n$, pero nunca hemos encontrado un cerrado fórmula. Me preguntaba si no era un simple enfoque, o si alguien sabe cómo encontrar la solución.

He hecho varios intentos. Mi primer intento fue el de intentar puramente combinatoria solución, pero la interconectividad de hecho es un poco ridículo. Traté de resolver el complementario problema colocando $0$'s de la diagonal principal, permuting ellos, y teniendo en cuenta todas las otras opciones para el resto de las entradas, pero esto resultó en múltiples formas de alcanzar el mismo de la matriz. Traté de resolver los problemas más simples de columna sólo puentes o fila puentes, que había soluciones simples, pero que la combinación de ellos resultó difícil. Y, más recientemente, (que yo aún no totalmente desarrolladas), traté de establecer una relación recursiva de la $n-1$ de los casos a la $n$ de los casos.

Cualquier visión sería muy apreciada.

Answer 1

Deje $F(a,b)$ el número de con $a$ horizontales específicas de puentes y $b$ específica vertical puentes. Las otras filas y columnas puede o no puede ser puentes. A continuación, el número de afectados plazas es $(n-a)(n-b)$ $$F(a,b)=2^{(n-a)(n-b)}$$
Deje $B(n)$ el número de puente de arreglos.
Ahora, ¿de inclusión-exclusión:

• Comience con una sola puentes: Hay $F(1,0)$ un puente en la primera fila, otro $F(1,0)$, con un puente en la segunda fila, y así sucesivamente, por lo $nF(1,0)$ en todos horizontal puente (contar las repeticiones). Hay$F(0,1)$, con un puente en la primera columna, etc, por lo que otra de las $nF(0,1)$, con un desnivel del puente.
  $nF(1,0)+nF(0,1)$.
• Dos-puente de los patrones se han contado dos veces, por lo que el número debe ser restado. Si ambos puentes son horizontales: hay $n\choose2$ pares de puentes, cada par tiene $F(2,0)$ patrones. Si ambos puentes son verticales, no son otra de las ${n\choose2}F(0,2)$ patrones. Si uno es vertical y la otra horizontal, hay $n$ opciones para la horizontal y $n$ opciones para la vertical. En todos los casos, se $F(1,1)$ patrones.
  Restar ${n\choose2}F(2,0)+{n\choose1}{n\choose1}F(1,1)+{n\choose2}F(0,2)$
• Tres-puente de los patrones deben ser agregado en:
  Agregar ${n\choose3}F(3,0)+{n\choose2}{n\choose1}F(2,1)+{n\choose1}{n\choose2}F(1,2)+{n\choose3}F(0,3)$
• etc...

El total sin puentes, tiene un poco más simple fórmula, y que la suma es $$2^{n^2}-B(n)=\sum_{i=0}^n\sum_{j=0}^n(-1)^{i+j}{n\choose i}{n\choose j}2^{(n-i)(n-j)}$$ La simetría con $(i,j)$ reemplazado por $(n-i,n-j)$ da $$\begin{array}{rcl}2^{n^2}-B(n)&=&\sum_{i=0}^n(-1)^i{n\choose i}\sum_{j=0}^n(-1)^j{n\choose j}2^{ij}\\&=&\sum_{i=0}^n(-1)^i{n\choose i}(1-2^i)^n\end{array}$$ Para comprobar la $n=1,2,3$:
$n=1:2-B(1)=0-(-1)=1\to B(1)=1$
$n=2:16-B(2)=1.0^2-2.1^2+1.3^2=7\to B(2)=9$
$n=3:512-B(3)=1.0^3+3.1^3-3.3^3+1.7^3\to B(3)=247$

Answer 2

Hay $2^{n^2}$ estados posibles de la matriz.

Cómo muchos de los que están de puente?

Si $\lvert H\rvert$ enumera la horizontal puentes y $\lvert V\rvert$ enumera las verticales, entonces tenemos:

$$\lvert H \cup V\rvert=\lvert H\rvert +\lvert V\rvert-\lvert H \cap V\rvert$$

Para enumerar $H$ me voy a tomar el complemento de los casos en los que hay al menos un cero en cada fila.

Para cualquier fila, el número de casos con al menos un cero, es a su vez el complemento de los casos en los que no hay ceros en la fila:

$(2^n-1)$

La combinación de todas las n filas:

$(2^n-1)^n$

Y tomando el complemento:

$\lvert H\rvert=2^{n^2}-(2^n-1)^n$

Por simetría:

$\lvert V\rvert=2^{n^2}-(2^n-1)^n$

Ahora para calcular el $\lvert H \cap V\rvert$

Hay $2^n-1$ formas de puente de izquierda a derecha, si hacemos caso de la no-superación de plazas y considerar sólo la verdad para cada fila de si hay una línea que va de izquierda a derecha.

Del mismo modo también hay $2^n-1$ formas de puente de arriba a abajo, si hacemos caso de la no-superación de plazas y considerar sólo las líneas completas.

Multiplique esos para obtener el número de combinaciones de ambos, pero restar $(2^n-2)=-(2^n-1)+1$ desde por la inclusión-exclusión en el principio de este método doble-cuenta que muchos de los casos. Esto es debido a que para cada combinación de líneas horizontales, cada combinación de líneas verticales es claramente permitida, con la excepción de cuando cada línea horizontal se completa de 1. Cuando todos 1, cada línea vertical combinación es imposible, excepto para el único caso en que todas las líneas verticales son los puentes. Así que debemos deducir $2^n-1$ y añadir $1$.

$\lvert H \cap V\rvert=(2^n-1)(2^n-1)-(2^n-1)+1=(2^n-2)(2^n-1)+1$

Ahora por nuestro método de $$\lvert H \cup V\rvert=\lvert H\rvert +\lvert V\rvert-\lvert H \cap V\rvert$$

$$\lvert H \cup V\rvert=2\times(2^{n^2}-(2^n-1)^n)-((2^n-2)(2^n-1))$$

Ahora divida esto por el número total de arreglos posibles para dar la probabilidad:

$$P=\frac{2\times(2^{n^2}-(2^n-1)^n)-((2^n-2)(2^n-1)+1)}{2^{n^2}}$$

Que los cheques dando a $\frac{1}{2}$$n=1$$\frac{7}{16}$$n=2$.