Tuesday, May 25, 2010

Packing Rectangles

Suppose that you have an n by n square made up of unit squares (we can think of this as a chessboard) on which you want to place R non-overlapping rectangles also made up of unit squares. How many ways can this be done? The board need not be covered.

There are many known variations of this problem, but the one that's most closely related that I can find solves this problem for R=1, in which case the answer is (n(n+1)/2)^2. I imagine that the problem has also been considered for general R, but can't seem to find it. Tips or ideas?

2 comments:

rehan said...

It seems like you could redo the R=1 calculation for an n x m grid and then use that as the basis for making an induction equation (i.e. get f(n,n) in terms of f(n, n-1))

daveagp said...

You might want to try "mathoverflow" for some additional comments