Let's say I have a board like this one (though significantly smaller, it's 4×7)
and I have two 2×3 bricks.
I'd like to know how many ways to arrange the bricks on the board. The bricks should stay inside the board and they should not overlay.
Doing some calculations/estimations, I came up with ~285 arrangements, but I couldn't figure out a more "scientific" method. I'd also like to "create" a formula taking into account variables like the board size, the number of bricks and their size. Thanks in advance.
Best Answer
A general approach to this type of problem is the inclusion-exclusion principle. The idea is to count all the possible configurations of the bricks (ignoring overlaps), then subtract configurations where a single pair of bricks overlap (ignoring overlaps with the rest of the bricks), then add back in configurations that have multiple overlaps (since they were removed multiple times), and so on. This effectively reduces the problem of counting full configurations to the problem of enumerating clusters, and allows you to write the number of configurations as a polynomial in the dimensions of the board.
Let $K_{m,n}(M,N)$ be the number of ways to place an $m \times n$ brick or cluster of bricks with $180^\circ$ rotational symmetry on an $M \times N$ board (taking $m\le n$ and $M\le N$ with no loss of generality). If $n \le M$, this is given by $$K_{m,n}(M,N)=(M-m+1)(N-n+1)+(M-n+1)(N-m+1) \\ =2MN-(M+N)(m+n-2)+2(m-1)(n-1).$$ If the object only fits lengthwise (because $m \le M < n \le N$), then $$K_{m,n}(M,N)=(M-m+1)(N-n+1);$$ and obviously $K_{m,n}(M,N)=0$ if the object doesn't fit at all. An object with no rotational symmetry can be placed in twice this many ways, and one with $90^\circ$ rotational symmetry can be placed in half this many distinct ways.
The number of ways to place two distinguishable $2\times 3$ bricks without worrying about overlaps is just $\left(K_{2,3}(M,N)\right)^2$. You then need to subtract the overlap configurations. To do this, enumerate the different (up to rotational symmetry) ways to place one brick so that it overlaps another, keeping track of the size and symmetry of each such "cluster". You can do this by hand. It turns out that there is one symmetric $2\times 3$ cluster (bricks right on top of each other); non-symmetric clusters with parallel bricks of size $3\times 3$, $3\times 4$ (two of them), $3\times 5$ (two of them), $2\times 5$, and $2\times 4$; and non-symmetric clusters with perpendicular bricks of size $3\times 3$ (two of them), $3\times 4$ (four of them), and $4\times 4$ (two of them). The number of overlap configurations is therefore $$ K_{2,3}+2\cdot\left(3K_{3,3}+6K_{3,4}+2K_{3,5}+K_{2,5}+K_{2,4}+2K_{4,4}\right). $$ Now, if we fix the size of the board to be $4\times 7$, and calculate $$ \begin{eqnarray} K_{2,3}(4,7) &=& 27 \\ K_{3,3}(4,7) &=& 20 \\ K_{2,4}(4,7) &=& 18 \\ K_{3,4}(4,7) &=& 13 \\ K_{4,4}(4,7) &=& 8 \\ K_{2,5}(4,7) &=& 9 \\ K_{3,5}(4,7) &=& 6, \\ \end{eqnarray} $$ we find the total number of legal configurations to be $$ 27^2 - 27-2\cdot\left(3\cdot 20 + 6\cdot 13 + 2\cdot 6 + 9 + 18 + 2\cdot 8\right) = 316, $$ as calculated in other answers.