# Tiling a Tilted Square

This week’s Fiddler is a challenging counting problem.

Consider the following array of 25 squares:

You are filling the array with rectangles by repeating the following two steps:

1. Select one of the 12 squares along the outer perimeter that has not yet been selected as part of a rectangle.
2. Form the largest rectangle you can that includes the square you just selected and other squares that are not yet part of any such rectangle.

You repeat these steps until every square along the perimeter has been selected. Here are two final states you might encounter:

How many distinct final states are possible? (Note: States that are rotations or reflections of each other should be counted as distinct.)

My solution:
[Show Solution]

## 7 thoughts on “Tiling a Tilted Square”

1. MarkS says:

Hi Laurent, I got the same solution as you, but alas also did not make any more progress on a closed-form version.

Looking at numerics up to n=2000, it seems that d_n/c_n^2 and e_n/c_n^4 both approach constants at large n, with corrections forming a power series in 1/n. For e_n, fits to this form yield a limiting constant that is numerically close to (2π)^(-11/2). An analytic evaluation of this constant should be much easier than finding the full closed-form solution, but I have not been able to do it.

1. Nice find! I think I was able to work out one of the limits:
$\lim_{n\to\infty}\frac{c_n^2}{d_n} =\left(5-\frac{4}{\pi}\right)^2\approx 13.88874349$I updated my solution to include a derivation. Unfortunately, the technique I used doesn’t work for $e_n$ as far as I can tell, so I’m still stuck on that one.

1. MarkS says:

Wow, that’s very nice!

So then my power-of-2π guess for the e-series constant is almost certainly wrong, given that the d-series constant is this complicated. (And I still have no ideas for how to evaluate it!)

2. Sameer G says:

For the recurrence relations initial conditions, I think you meant to say =1, not =0.
i.e. c_0 = 1, d_0 = 1, e_0 = 1

1. Thanks for catching that! I fixed the typos.

3. MingL says:

Hello Laurent,

I have a question regarding the definition of C_n in your solution step 1.

In the above solution, it seems that C_n defines as the number of tilings of the quarter shape with n squares along the outer perimeter.

However, in the Applications in combinatorics section of Catalan numbers webpage ( https://en.wikipedia.org/wiki/Catalan_number ), there is a similar example as our question, but C_n defines as the number of ways to tile the quarter shape.

To me, these two definitions of C_n are kind of different. To what I understand, the original is asking how many ways to tile, and I think your e_4= 106 is the answer for the original question, which is what I got by a different approach.

Please correct me if I misinterpret anything.

1. You are correct — $c_n$ is the number of ways of tiling the quarter shape, and this coincides precisely with the Catalan numbers. In the link you posted, they have the same example, which they call “number of ways to tile a stairstep shape of height $n$ with $n$ rectangles”. This is the same as tiling the quarter shape because if you are constrained to using exactly $n$ rectangles, then each rectangle must have a corner along a different diagonal square (as there are $n$ of these), so both definitions are the same.

I only use $c_n$ as a stepping stone to build up to what the original problem is actually asking — first by defining $d_n$ as the number of tilings of the half shape, and then finally $e_n$ as the number of tilings of the full shape. So yes, the $e_n$ sequence is the solution to the original problem and the $c_n$ sequence is just an intermediate step.