Question 182
There is a $n \times n$ square forest grid in which you wish to grow a forest. You have $n^2$ saplings (young trees) so that the $i$-th sapling, once planted, will grow to a tree of height exactly $i$ metres tall. Each sapling has to be planted in a different square of the forest grid. A balanced forest is one in which for every tree in the forest at least one of the following conditions holds true:
* There exists a smaller tree in the same column.
* There exists a taller tree in the same row.
In how many ways can you grow a balanced forest?
* There exists a smaller tree in the same column.
* There exists a taller tree in the same row.
In how many ways can you grow a balanced forest?