The answer to the question is \frac{q!}{q^q}
Since there are infinite spaces in each column, you can treat each column as a number (say 1, 2, ... , q).
The question is equivalent to "if I have a bag with the numbers 1 up to q in it, and I pick out q numbers with replacement, what is the...