Question 15
For a positive integer $n$, we consider an $n \times n$-board and tiles with sizes $1 \times 1$, $1 \times 2$, ..., $1 \times n$. In how many ways can exactly $\frac{1}{2}n(n+1)$ squares of the board be coloured red, so that the red squares can be covered by placing the $n$ tiles horizontally on the board, as well as by placing the $n$ tiles vertically on the board? Two colourings which are not identical, but which can be obtained from one another by rotation or reflection, are counted as different colourings.