How calculate the number of possible different variations? I feel stupid, but I don't know how to calculate how many possible variations I can get from for example three spaces (1|2|3) Normally I'd say: "well that is easy, just take the number of spaces (=3) and 3^3"
But that doesn't work with two spaces, like "1|2", there are only 2 different ways on how to arrange two numbers, but 2^2 would be 4. 
(I want to know how many spaces I need to get ~25000 possible variations)

By variations, do you mean..
..placement without repetition
There are $n! = n*(n-1)* ... * 3 * 2 *1$ ways of ordering $n$ elements. So for 3, you have 3*2*1 = 6. 
$8! = 8*7*6*5*4*3*2*1 = 40320$, which is as close to 25000 as you can get with a factorial.
..placement with repetition
Your original guess was right; the answer is $n^n$. 
e.g. for 3 items, you have 3 choices for the first space, 3 choices for the second space, and 3 choices for the final space, so 3*3*3 = 27. For 2 also, i.e. 2*2 = 4 ways ((1|1), (1|2), (2|1), (2|2)). 
$6^6 = 46656$ is as close to 25000 as you'll get.
