Here is a bijective proof of the main result. We first prove a related result: modify condition (2) by changing exactly to less than. Then we will show the corresponding answer is (n+1)n-1, the number of rooted forests on {1, ..., n}.
The bijection is as follows: imagine an empty stack, and read the board across rows, from top to bottom. Whenever you encounter a checker in column i, push i onto the stack. Whenever you reach the end of a row, pop off the top number of the stack, say j. Then j's children are just the numbers pushed onto the stack in the next row. It's easy to check that this is a bijection. (Note the roots of the forest are the checkers in the first row.)
It's not hard to modify this to work with the original problem and rooted trees on {1, ..., n}, giving the desired answer of nn-1. Number the checkers in order across rows, from top to bottom, and find the first checker C whose number is the same as its row number. Then take the column of C to be the root of the tree. To find the rest of the tree, use the procedure in the previous paragraph, starting right after C with an empty stack. Then, do the procedure again, starting right before C with an empty stack, but reading the board backwards. These two procedures give you two rooted forests, and taking the column of C to be the parent of all the roots of these forests gives a rooted tree, which completes the bijection. I'll omit the proof, but it's quite straightforward.
