Combinatoria - número de rectángulos disjuntos

Question

Mi pregunta es: Tengo una cuadrícula $m \cdot n$ y tengo que encontrar cuántos pares de rectángulos disjuntos hay. Los cuadrados también están permitidos. Tampoco pueden compartir aristas ni vértices.

Sé, que el número de todos los rectángulos en la cuadrícula es ${m+1 \choose 2} \cdot {n+1 \choose 2}$ pero no puedo averiguar cuántos pares disjuntos hay. Gracias.

Answer 1

Dos rectángulos disjuntos deben tener $4$ distintos lados horizontales extendidos o $4$ distintos lados extendidos verticales. Hay $\binom{n+1}4$ conjuntos de $4$ lados extendidos horizontales distintos, y para cada uno de ellos podemos elegir dos lados extendidos verticales cualesquiera para el rectángulo superior y dos cualesquiera para el rectángulo inferior; esto da cuenta de

$$\binom{n+1}4\binom{m+1}2^2$$

pares de rectángulos que pueden separarse por una línea horizontal. Del mismo modo, hay

$$\binom{m+1}4\binom{n+1}2^2$$

pares de rectángulos que pueden separarse mediante una línea vertical. Por último, hay

$$2\binom{n+1}4\binom{m+1}4\tag{1}$$

pares de rectángulos que pueden estar separados por una línea horizontal y otra vertical, por lo que hay

$$\binom{n+1}4\binom{m+1}2^2+\binom{m+1}4\binom{n+1}2^2-2\binom{n+1}4\binom{m+1}4$$

pares de rectángulos disjuntos. (El factor de $2$ en $(1)$ surge del hecho de que el rectángulo superior puede estar tanto a la izquierda como a la derecha del rectángulo inferior).

Answer 2

Un poco como calcular el número de rectángulos de tu cuadrícula, consideras 2 rectángulos disjuntos y extiendes sus lados: obtienes $k$ líneas verticales y $l$ distintas líneas horizontales, con $k,l\in\{2,3,4\}$ .

¿Cuántos pares de rectángulos disjuntos hay que den las mismas líneas? Sea $n_{k,l}$ pares. Así pues, la respuesta buscada es: $$\sum_{(k,l)\in \{2,3,4\}^2} n_{k,l}{{m+1\choose k}}{{n+1}\choose l}$$

Ahora tenemos que calcular los valores del $n_{k,l}$ .

Observe que $n_{k,l}=n_{l,k}$ . De hecho, cada configuración del $(k,l)$ corresponde a una configuración del $(l,k)$ supongamos que $k\leq l$ .

$n_{2,2}=0$ ya que de lo contrario implicaría que obtenemos dos rectángulos que son idénticos.

$n_{2,3}=0$ =ya que de lo contrario implicaría que obtenemos rectángulos que comparten la línea vertical central.

$n_{3,3}=0$ ya que de lo contrario compartirían una línea vertical y una línea horizontal por lo que compartirían un vértice.

$n_{2,4}=1$ las líneas determinan nuestros rectángulos, si queremos que sean disjuntos.

$n_{3,4}=6$ Considera una línea horizontal compartida por dos rectángulos. Mira las líneas verticales de izquierda a derecha, y las dos primeras pertenecen a uno y las dos últimas, al otro. En este caso, sus segundas líneas horizontales son distintas (de modo que $k=3$ ), por lo que para cada caso se obtiene $2$ configuraciones, por lo que teniendo en cuenta que hay $3$ casos disjuntos, por cada línea horizontal compartida se obtiene $6$ configuraciones.

$n_{4,4}=10$ ; este es un poco más difícil. Considera las líneas horizontales y míralas de arriba abajo: digamos que tu rectángulo superior es $A$ y el segundo, $B$ . Escribe en orden los rectángulos a los que pertenecen sus líneas. Así sólo obtendrás $AABB$ (caso $1$ ), $ABAB$ (caso $2$ ) o $ABBA$ (caso $3$ ). Ahora, para enumerar cada caso, comprobamos las líneas verticales de izquierda a derecha:

caso $1$ Todas las configuraciones son posibles. El $A$ rectángulo está en un carril superior que el $B$ rectángulo por lo que sólo tienen que darnos $4$ líneas verticales: ${4\choose 2}=6$ posibilidades.

caso $2$ y $3$ : sólo $AABB$ y $BBAA$ pueden salir, de lo contrario, no serían disjuntos.

Esto te da la fórmula completa. Desafortunadamente, no sé si tienes una expresión más compacta para esto :(