Define an $n$-staircase to be the union of all squares of an $n \times n$ grid lying on or below its main diagonal. How many ways are there to divide a 10 -staircase into 10 rectangles, each having a side of length 1 ? (Reflections are not included.)
A 10-staircase has 10 "upper right corners" $P$, each of which must be the upper right corner of some rectangle, and no two of which can belong to the same rectangle. It also has a single lower left corner $Q$ which must belong to the same rectangle as one of the ten points $P$. Since this rectangle has one side of length 1 , it must be a $10 \times 1$ rectangle placed either vertically or horizontally along the long side of the staircase. The remainder of the figure is then a 9 -staircase to be filled with 9 rectangles.

We can then repeat the argument to find that one of the long sides of the 9-staircase must be filled by a $9 \times 1$ rectangle, leaving an 8 -staircase. This continues until we reach the 1 -staircase, a single square, which can be filled in only one way.

![](https://cdn.mathpix.com/cropped/2024_04_17_8121fc684f430fcf293fg-1.jpg?height=528&width=529&top_left_y=1002&top_left_x=1405)

The placement of the $10 \times 1$ rectangle is irrelevant because of the symmetry of the shape. But the $9 \times 1$ through $2 \times 1$ rectangles each involve a choice between two alternatives, so the number of tilings is $2^{8}=256$.