I've had this question in my head for over a year, but never found a satisfying answer. In fact, I lost all my notes, so I started over last week, and now I ask for help/insight.
The problem
Given a rectangular classroom with a 'student area' of size $W_{r_{orig}} \ge 3$ by $H_{r_{orig}} \ge 3$ cells, how many unique arrangements $a$ of $N$ desks of size $W_{d_{orig}} \ge 1$ by $H_{d_{orig}} \ge 1$ cells exist within that 'student area'?
A desk:
- may not be rotated (must face the blackboard)
- must have at least 1 cell free in each of the 8 directions (to allow moving between the desks)
Different statement
I thought it would be simpler to consider an equivalent problem, with a $W_r = H_{r_{orig}} - 1$ by $H_r = H_{r_{orig}} - 1$ student area and $N$ desks of size $W_d = W_{d_{orig}} + 1$ by $H_d = H_{d_{orig}} + 1$ cells (that can touch, but still not rotate).
That means:
- ensuring the leftmost and topmost cells of the original room are always empty
- the original desks always have a free cell behind and to the right of them
Also, we have bounds:
- $2 \le W_d \le W_r$
- $2 \le H_d \le H_r$
- $1 \le N \le \lfloor W_r / W_d \rfloor \cdot \lfloor H_r / H_d \rfloor$, the upper bound being a tight packing/filling the room entirely
Image to show equivalency in a different way and serve as an example
Tests and ideas
With $N, W_r, H_r, W_d, H_d$ positive integers with bounds mentioned above, we have:
Arrangement counting function: $a(N, W_r, H_r, W_d, H_d) \rightarrow \mathbb{N}$
With pen and paper drawing and counting, plus some induction, I could figure out:
1 room sized desk has 1 possible position: $a(1, W, H, W, H) = 1$
1 smaller rectangular desk in a rectangular room ($2 \le W_d \le W_r, 2 \le H_d \le H_r$ ) $a(1, W_r, H_r, W_d, H_d) = (W_r - W_d + 1) \cdot (H_r - H_d + 1)$
maximum smallest square desks in an even-side-lengths room ($W_r = 2 \cdot W , H_r = 2 \cdot H$)
- $1 \le W, 1 \le H$
- $a(W \cdot H, W_r, H_r, 2, 2) = 1$
- only 1 arrangement, filling the entire area
maximum smallest square desks in a single-odd-side-length room (assume $W_r$, have symmetry by swapping $W_r$ and $H_r$ anyway) ($W_r = 2 \cdot W + 1 , H_r = 2 \cdot H$)
- $1 \le W, 1 \le H$
- $a(W \cdot H, 2(W) + 1, 2(H), 2, 2) = (W+1)^H$
Another image example, with some justification on the exponentiation
- I am currently stuck on "maximum smallest square desks in an odd-side-lengths room" part. There's a lot of combinations, even at a 5x5 area, and trying to use symmetries to my advantage ($W_r = 2 \cdot W + 1 , H_r = 2 \cdot H + 1$)
- $1 \le W, 1 \le H$
- $a(1 \cdot 1, 2(1) + 1, 2(1) + 1, 2, 2) = 4$ (start in the top left corner, it is apparent mirroring by the horizontal and/or vertical axes provides new states)
The question
I was thinking by getting the upper and lower patterns (by desk size/count), the "middle" ones would become apparent, but this is already hard.
Couldn't find anything on StackExchange or Google, but would be pleasantly surprised if it's already solved and I just had the wrong keywords, otherwise, looking for hints or even a full solve.
Hope someone else finds this brain bug fun!