For a positive integer $n$, we consider an $n \times n$ board and tiles with dimensions $1 \times 1, 1 \times 2, \ldots, 1 \times n$. In how many ways can exactly $\frac{1}{2} n(n+1)$ squares of the board be colored red, such that the red squares can all be covered by the $n$ tiles placed horizontally, and also by the $n$ tiles placed vertically? Two colorings that are not identical but can be transformed into each other by rotating or reflecting the board are counted as different.
The number of red squares is exactly equal to the total number of squares that can be covered by the $n$ tiles, so the tiles are placed only on red squares. Consider a coloring of the board and the corresponding horizontal covering of the tiles (where all tiles lie horizontally) and the vertical covering. We derive several properties of the coloring and then count the number of possibilities. Let the tile with dimensions $1 \times k$ be the $k$-tile.

Since the horizontal covering contains an $n$-tile, each column must contain at least one red square. Therefore, in the vertical covering, there must be at least one tile in each column; since there are exactly $n$ tiles, this means that there must be exactly one tile in each column. Similarly, there must be exactly one tile in each row in the horizontal covering. Number the rows and columns based on the number of the tile that lies in them: so row $i$ is the row in which the $i$-tile lies in the horizontal covering, and analogously for the columns.

We now prove that the square in row $i$ and column $j$ (call this square $(i, j)$) is red if and only if $i+j \geq n+1$. We prove this by induction on $i$. In row 1, there is only one red square, and it must be in the column where the $n$-tile lies in the vertical covering, so in column $n$. Thus, the square $(1, j)$ is red if and only if $j=n$, or equivalently, if and only if $1+j \geq n+1$. Now let $k \geq 1$ and assume we have proven this for all $i \leq k$. We want to prove it for $i=k+1$, that is, that a square $(k+1, j)$ is red if and only if $k+1+j \geq n+1$, or equivalently, if $j \geq n-k$. Consider a column $j \geq n-k$. By the induction hypothesis, we know exactly how many red squares this column has in rows $1,2, \ldots, k$: the square $(i, j)$ is red if and only if $i+j \geq n+1$, or $i \geq n+1-j$, so there are $k-(n-j)=j+k-n$ such squares. In the remaining $n-k$ rows, this column needs $j-(j+k-n)=n-k$ more red squares. Therefore, this column has a red square in each of those rows and in particular also in row $i=k+1$. In row $i=k+1$, the squares $(i, j)$ with $j \geq n-k$ are all red, and there are $k+1$ such squares. Thus, these are exactly all the red squares in row $i=k+1$, so the square $(i, j)$ is red if and only if $j \geq n-k$, or equivalently, if and only if $i+j \geq n-k+k+1=n+1$. This completes the induction.

Now consider two rows directly above each other with row numbers $a$ and $b$, with $a>b$. In column $n-b$, there is a red square in row $a$ (since $a+n-b>n$) but not in row $b$. In the row directly on the other side of row $b$ (if it exists), there should therefore be no red square in column $n-b$, otherwise the red squares in column $n-b$ would not be contiguous and the tile with number $n-b$ could not lie here. The row number of this row must therefore be less than $b$. We conclude that the row numbers cannot first decrease and then increase again. Above and below row $n$, there must be a row with a smaller number (or no more rows at all), so the row numbers must decrease on both sides from there. We see that the row numbers must first be increasing up to row $n$ and then decreasing. The same can be proven for the column numbers.

Conversely, we need to prove that if the row and column numbers are first increasing and then decreasing, we can place both the horizontal and vertical tiles. For this, we color the square $(i, j)$ red if and only if $i+j \geq n+1$. For a fixed $i$, the red squares are thus the squares $(i, j)$ with $j \geq n+1-i$; due to the shape of the column numbers, these columns are contiguous. Therefore, the red squares in each row are contiguous. We can thus place the horizontal tiles exactly on the red squares. The same works for the vertical tiles. We could not have chosen a different coloring with the same row and column numbers that would allow the tiling, because we already know that in every valid tiling, $(i, j)$ is red if and only if $i+j \geq n+1$.

In total, we are looking for the number of ways to choose both the row and column numbers in an order that is first increasing and then decreasing; for each of these choices, there is exactly one way to color the red squares that satisfies the condition. The number of ways to arrange the numbers 1 to $n$ in an order that is first increasing and then decreasing is equal to the number of subsets of $\{1,2, \ldots, n-1\}$, namely the subset of numbers that come before the number $n$; these can be sorted in only one way (increasing) and the rest of the numbers must be sorted in decreasing order and placed after $n$. The number of subsets is $2^{n-1}$. Therefore, the total number of colorings that satisfy the problem is $\left(2^{n-1}\right)^{2}=2^{2 n-2}$.