How Many Ways Can You Tile the Tilted Square?

This is a problem that can be divided into subproblems. For example, if we decide to pick this rectangle:

There are four components this gets split into: a triangular formation on the top and bottom, and a single tile on the left and right.

Let's focus on the top component. This can be split in three ways:

1. In the first, this is just a smaller subproblem: a triangular formation of height 2. Let's call this a corner triangle of height 2.
2. In the second, this is two smaller subproblems, each of them being a triangle. However, these triangles are different: the edge squares lie along the "hypotenuses" of these triangles. Let's call each of these a side triangle of size 2.
3. In the third, this is three smaller subproblems, each of them being singular squares (only one way to tile). Technically, the one on the top is a corner triangle of side 1, and the ones on the left and right are side triangles of side 1.

Notice that we can find the number of ways to tile any particular subsection, and the total number of ways to tile is the product for each of the subsections.

So with this, we can establish the three functions needed to determine the overall answer:

• one for the overall diamond (let $f(n)$ describe this for a diamond with $n$ squares along one edge)
• one for the corner triangle (let $g(n)$ describe this for a corner triangle with height $n$)
• one for the side triangle (let $h(n)$ describe this for a side triangle with size $n$)

Side triangles

Define $h(0)=1$. Now for an side triangle of size $n$, we can split by a rectangle, creating one side triangle of size $k$ and the other of size $n-1-k$. As a result, the total number of distinct formations is the sum of all these from $k=0$ to $k=n-1$, or:

$$h(n)=\sum_{k=0}^{n-1}{h(k)\cdot h(n-1-k)}$$

Note that $h(1)=1$, $h(2)=2$, and $h(3)=5$, which can be seen manually. In fact, these are Catalan numbers! $h(n)$ is indeed just the $n$–th Catalan number, which we will denote as $C_n$.

The first few Catalan numbers:

Corner triangles

Define $g(0)=1$. Now for a corner triangle of height $n$, we can split by a rectangle, creating one corner triangle of size $k$ and two corner triangles, each of size $n-1-k$. So the total number of distinct formations is the sum of all these from $k=0$ to $k=n-1$, or:

$$g(n)=\sum_{k=0}^{n-1}{g(k)\bigl(f(n-1-k)\bigl)^2} \\ g(n)=\sum_{k=0}^{n-1}{g(k)(C_{n-1-k})^2}$$

The first few values of $g(n)$:

Diamonds

For a diamond, after choosing a rectangle, we split into four corner triangle subregions: two of size $k$ and two of size $n-1-k$. So the total number of distinct formations is the sum of all these from $k=0$ to $k=n-1$, or:

$$f(n)=\sum_{k=0}^{n-1}{\bigl(g(k)\bigl)^2\bigl(g(n-1-k)\bigl)^2}$$

The first few values of $f(n)$ (with $f(0)=1$):

The questions asked us about diamonds of sides of $n=4$ and $n=5$, leading us to the answers below!

Answers

This Week's Fiddler: 106

Extra Credit: 3002

And beyond

While I did not determine a closed form, we now have a recursive definition of the sequence! With $C_n=\frac{1}{n+1}{2n\choose n}$ as the $n$–th Catalan number, we can define the following functions to describe $f(n)$:

$$g(0)=1, f(0)=1 \\ g(n)=\sum_{k=0}^{n-1}{g(k)(C_{n-1-k})^2} \\ f(n)=\sum_{k=0}^{n-1}{\bigl(g(k)\bigl)^2\bigl(g(n-1-k)\bigl)^2}$$

And the values for up to $n=20$: