Placing checkers with some restrictions We are going to put n checkers on an (n x n) checkers board, with the following restrictions:
1) In each column there is EXACTLY one checker.
2) For i=1,2,...,(n-1), the first i rows cannot have EXACTLY i checkers.
The question is to count the number of ways to do so. I guess that the answer is n^{n-1}, but I do not know how to prove it. Can anyone help?
(If restriction 2) is removed, the answer is obviously n^n.)
 A: Let {ai} be the sequence giving the number of pieces in each row. Here's an easy bijection showing that such sequences are counted by Catalan numbers:
For any sequence, consider the lattice path starting at the origin that takes a1 steps up, then 1 step right, then a2 up, then 1 right, and so forth. Then the condition on this path is that you must touch the diagonal y=x after a right step exactly once, namely at (n,n). In other words, you must step above the diagonal, and once you do, you can't touch it again until the end of the path.
Now, just reflect the part of the path above the diagonal across it. This gives a path from the origin to (n,n) that stays below the diagonal, and these are counted by Catalan numbers. To go back, just reflect everything between the last two times you touch the diagonal.
A: 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.
A: If you denote this number by f(n), then we have the following equation by subtracting the bad possibilities from all possibilities:
f(n)=n^n-sum_{k=1}^{n-1} f(k){n\choose k}(n-k)^{n-k}
If by induction, you suppose that f(k)=k^{k-1} for k
A: A bijective solution should be possible, by using rooted trees. 
Labelled rooted trees on n nodes are also counted by n^(n-1), see this link.
There are also as many "types" of trees (e.g. for n=3 there are two types of trees, and for n=4, four types of trees), as there are "types of words", as David Speyer listed for n=3; in that case the types of words are 300 and 210. The word gives the number of pieces by row.
For n=4, the types of words are 4000, 3100, 2200, 2110. There are 4 words of the first type, 24 of the second and fourth, and 12 of third. These numbers match the number of trees of each type.
Also, it seems like the number of words, not counted by multiplicity, are given by the Catalan numbers! (n=3: 300, 030, 003, 210, 012)
(Of course, the Catalan numbers counts classes of trees.)
Edited to add:
A sketch of the bijection:
Label the columns 1,2,3,...,n. Also let the labels in the labeled rooted trees be 1,2,..,n.
Let the value of a node in a tree be the distance to the root for all nodes except the root, and 1 for the root. 
Put a piece in row i and column j if node j has value i. It remains to show that this actually is a bijection...
A: First observation (due to the crowd in 1015 right now, equivalently domotorp): every board with condition (1) can be cut up in exactly one way horizontally into slices, such that if the empty columns in each slice are removed, the resulting boards are square boards with conditions (1) and (2).  (Cut after row i if the first i rows would violate condition (2)).  
Note that there are exactly nn boards with condition (1).  
So, by the exponential forumla, 

\sum (# boards of size n with condition (1) ) tn/n! =
exp [ \sum (# boards of size n with conditions (1) and (2) ) tn/n! ]

So this reduces the problem to showing that exp(\sum (nt)^n/(n*n!)) = (\sum (nt)^n/n!).  
Edit: yeah, one can finish this proof per David's comment.  What we want to show is that there are n^n rooted forests on n vertices with an ordering on the trees.  But these are in bijection with functions f:n->n.  Given f, for every vertex i not in a cycle (i.e. the image of f^k for arbitrarily large k), put an edge from i to f(i).  Then what's left to encode is a permutation on the vertices in the cycles, which are the roots of the resulting trees; but there are (# trees)! of these, and (# trees)! orderings of the trees.
A: Have you checked the case n=3? I get 12 cases, not 9. Listed by the number of pieces in each row, I get
1 of type 300
3 of type 210
3 of type 201
1 of type 030
3 of type 012
1 of type 003
