Una fórmula para el número de combinaciones posibles de un $i\times j$ rectángulo en un $m\times n$ de tal manera que no se superpongan?

Question

Supongamos que tengo una cuadrícula de tamaño $m\times n$ y un rectángulo de longitud $i\times j$ donde $i$ y $j$ son números enteros como se muestra aquí para donde $m = 7$ , $n = 5$ , $i = 2$ , $j = 3$ :

¿Existe una fórmula o ecuación que determine el número de combinaciones posibles para que el rectángulo llene la cuadrícula lo máximo posible y no haya solapamientos? $m,n,i,j$ ? Algunas combinaciones serían las que se muestran aquí:

Answer 1

Este es mi intento de solución... Si hay algún error, por favor hágamelo saber.

Para encontrar el número total de orientaciones posibles, consideramos el número de orientaciones horizontales y verticales por separado, y multiplicamos los resultados.

Orientaciones horizontales:- Para hallar el número de orientaciones horizontales, consideramos una cuadrícula de anchura $1$ y la longitud $m$ . Que la longitud del rectángulo sea igual a $i$ . El número de espacios en blanco $= m - i* \lfloor \frac{m}{i} \rfloor $ . Dejemos que esto sea igual a $k$ . Sea el número de cajas , es decir $ \lfloor \frac{m}{i} \rfloor $ igual $n_0$

Para encontrar el número de orientaciones de las cajas , dejamos que cada cuadrado encerrado por la caja sea igual a $1$ unidad ( En este caso , cada individual caja encierra $i$ unidades). Entonces , el número de orientaciones es equivalente a encontrar el número de soluciones para $x_1,x_2....x_{k+1}$ en $$ x_1 + x_2 + x_3 +.... x_{k+1} = i*n_0 $$ Debemos establecer la restricción de que $ x_{i_0}\equiv 0 $ (mod $i$ ) .

Esto se reduce a encontrar el coeficiente multinomial de $x^{i*n_0}$ en $ ( 1+ x^i + x^{2i} + x^{3i}...+ x^{i*n_0} )^{k+1} $ . Y esto equivale a $$ \sum_{b_{i_0}\geq 0 }\left(\begin{array}{cc} k+1 \\ b_1,b_2,...b_{n_0+1} \end{array} \right)$$

$b_{i_0}$ está sujeta a las restricciones :- $$ \sum b_{i_0}= k+1 $$ $$ b_2 + 2*b_3+.....n_0*b_{n_0+1} = n_0 $$ Esto es para un solo grupo de cajas en una fila. Para toda la cuadrícula, el coeficiente multinomial debe elevarse a la potencia $n_1 = \lfloor \frac{n}{j} \rfloor $

Fórmula:-

Se puede emplear un método similar para calcular el número de orientaciones verticales. El número total de orientaciones posibles sería el producto ( ya que no se puede insertar ningún rectángulo extra ) , y es igual a :- $$ (\sum_{b_{i_0} \geq 0 }\left(\begin{array}{cc} m-i*\lfloor \frac{m}{i} \rfloor +1 \\ b_1,b_2,...b_{n_0+1} \end{array} \right))^{n_1}* (\sum_{a_{i_0} \geq 0}\left(\begin{array}{cc} n-j*\lfloor \frac{n}{j} \rfloor +1 \\ a_1,a_2,...a_{n_1+1} \end{array} \right))^{n_0}$$

Ejemplo:-

Consideremos su caso, como ejemplo. Aquí, $ m=7 , n=5 , i = 2, j= 3 $ Tenemos $ m - i*\lfloor \frac{m}{i} \rfloor = 1$ y $ n - j*\lfloor \frac{n}{j} \rfloor = 2$ . $n_0 = 3 , n_1 = 1 $

Por tanto, el número de combinaciones = $$ (\sum_{b_{i_0}\geq 0} \left(\begin{array}{cc} 2 \\ b_1,b_2,b_3,b_4 \end{array} \right))^1 * (\sum_{a_{i_0} \geq 0} \left(\begin{array}{cc} 3\\ a_1,a_2 \end{array} \right))^3$$ Después de someter a $a_{i_0}$ y $b_{i_0}$ a las restricciones adecuadas , obtenemos :- $b_{i_0} \in (1,0,0,1)$ y $(0,1,1,0) $ y $a_{i_0}\in(2,1)$ . Por lo tanto, el número de orientaciones es $( \frac{2!}{1!0!0!1!}+\frac{2!}{0!1!1!0!})*\frac{3!}{2!1!} ^3= 4*3^3 = \boxed{108}$