# A formula for the number of possible combinations of a $i\times j$ rectangle in a $m\times n$ grid such that they don't overlap?

Suppose I have a grid of size $$m\times n$$ and a rectangle of length $$i\times j$$ where $$i$$ and $$j$$ are integers as shown here for where $$m = 7$$, $$n = 5$$, $$i = 2$$, $$j = 3$$:

Does there exist a formula or equation that determines the number of combinations that are possible such that the grid is filled by the rectangle as much as possible and there is no overlap? perhaps in terms of $$m,n,i,j$$ ? A few combinations would be as shown here:

• you say arbitrary, and then give exact values. maybe you should change it to an example – Lee Jan 9 at 8:44
• Sorry I meant m or n could be arbitrary i.e. any length – Student Jan 9 at 8:46
• – Student Jan 9 at 10:08
• Are the rectangles allowed to be rotated? – Servaes Jan 9 at 14:03
• No just the orientation that they are in since i is just always the length in the m direction and j is always the length in the n direction – Student Jan 9 at 14:24

This is my attempt at a solution... If there is any error , please let me know.

To find the total possible number of orientations , we consider the number of horizontal and vertical orientations separately, and multiply the results.

Horizontal Orientations:- To find the number of horizontal orientations , we consider a grid of breadth $$1$$ and length $$m$$ . Let the length of the rectangle equal $$i$$ . The number of blank spaces $$= m - i* \lfloor \frac{m}{i} \rfloor$$. Let this equal $$k$$ . Let the number of boxes , i.e $$\lfloor \frac{m}{i} \rfloor$$ equal $$n_0$$

To find the number of orientations of the boxes , we let each square enclosed by the box equal $$1$$ unit ( In this case , each individual box encloses $$i$$ units). Then , the number of orientations is equivalent to finding the number of solutions for $$x_1,x_2....x_{k+1}$$ in $$x_1 + x_2 + x_3 +.... x_{k+1} = i*n_0$$ We must lay the constraint that $$x_{i_0}\equiv 0$$ (mod $$i$$) .

This bottles down to finding the multinomial coefficient of $$x^{i*n_0}$$ in $$( 1+ x^i + x^{2i} + x^{3i}...+ x^{i*n_0} )^{k+1}$$ . And this happens to equal $$\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}$$ is subject to the constraints :- $$\sum b_{i_0}= k+1$$ $$b_2 + 2*b_3+.....n_0*b_{n_0+1} = n_0$$ This is for a single cluster of boxes in a row. For the entire grid , the multinomial coefficient has to be raised to the power $$n_1 = \lfloor \frac{n}{j} \rfloor$$

Formula:-

A similar method can be employed to calculate the number of vertical orientations. The total number of possible orientations would be the product ( as no extra rectangle can be inserted ) , and is equal to :- $$(\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}$$

Example:-

Let us consider your case, as an example. Here, $$m=7 , n=5 , i = 2, j= 3$$ .We have $$m - i*\lfloor \frac{m}{i} \rfloor = 1$$ , and $$n - j*\lfloor \frac{n}{j} \rfloor = 2$$ . $$n_0 = 3 , n_1 = 1$$

Therefore the number of combinations = $$(\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$$ After subjecting $$a_{i_0}$$ and $$b_{i_0}$$ to suitable constraints , we obtain :- $$b_{i_0} \in (1,0,0,1)$$ and $$(0,1,1,0)$$, and $$a_{i_0}\in(2,1)$$ . Therefore , the number of orientations is $$( \frac{2!}{1!0!0!1!}+\frac{2!}{0!1!1!0!})*\frac{3!}{2!1!} ^3= 4*3^3 = \boxed{108}$$

• As many of you might already know , this solution is wrong , owing to overcounting . Should I delete it ? – Sinπ Jan 29 at 17:00