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...