Probability of a sorted sequence Now I tried tackling this question from different sizes and perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I have no good ideas).
Let there be $k, n \in\mathbb{Z_+}$. These are fixed.
Consider a set of $k$ integers $S=\{0, 1, 2, ... k-1\}$.
We form a sequence  $a_1, a_2, ..., a_n$ by picking numbers from $S$ at random with equal probability $1/k$.
The question is - what is the probability of that sequence to be sorted ascending, i.e. $a_1 \leq a_2 \leq ... \leq a_n$? 
Case $k \to \infty$:
This allows us to assume (with probability tending to $1$) that all elements $a_1, ..., a_n$ are different. It means that only one ordering out of $n!$ possible is sorted ascending. 
And since all orderings are equally likely (not sure why though), the probability of the sequence to be sorted is
$$\frac{1}{n!}.$$
Case k = 2:
Now we have zeroes and ones which come to the resulting sequence with probability $0.5$ each. So the probability of any particular n-sequence is $\frac{1}{2^n}$. 
Let us count the number of possible sorted sequences:
$$0, 0, 0, \ldots, 0, 0$$
$$0, 0, 0, \ldots, 0, 1$$
$$0, 0, 0, \ldots, 1, 1$$
$$\ldots$$
$$0, 0, 1, \ldots, 1, 1$$
$$0, 1, 1, \ldots, 1, 1$$
$$1, 1, 1, \ldots, 1, 1$$
These total to $(n+1)$ possible sequences. Now again, any sequence is equally likely, so the probability of the sequence to be sorted is 
$$ \frac{n+1}{2^n}. $$
Question:
I have no idea how to generalize it well for arbitrary $k, n$. Maybe we can tackle it together since my mathematical skills aren't really that high. 
 A: The number of possible sequences is $k^n$. Then number of favourable outcomes, namely weakly increasing sequences, is $\binom{n+k-1}{k-1}=\binom{n+k-1}n$. The probability of finding the random sequence to be increasing is
$$
  \frac{\binom{n+k-1}{k-1}}{k^n} =
  \frac{\binom{n+k-1}n}{k^n} = \prod_{i=1}^n\frac{k+i-1}{ik}.
$$
To see why the binomial coefficient gives the number of weakly increasing sequences, imagine drawing a bar chart for the function, and tracing a path from position $(0,1)$ (at height $1$ to the left of the first bar) to $(n,k)$ (at height $k$ to the right of the last bar) across the tops of the bars. The path has $n+k-1$ steps, of which $n$ are horizontal across the top of a bar, and $k-1$ are vertical to increase the height.
A: Each sorted string consists of $n_0$ copies of $0$, followed by $n_1$ copies of $1$, etc., ending with $n_{k-1}$ copies of $k-1$. The restriction on the $n_j$ are that they be nonnegative and sum to $n$. The number of solutions to that has a known expression via binomial coefficients, in this case it is $\binom{n+k-1}{k-1}.$ So if this is placed over the number $k^n$ of possible strings, that is the probability the string is nondecreasing.
Here's a reference for the binomial coefficient use above. The thing being counted is the number of "weak compositions" of $n$, in the terminology used at that site:
http://en.wikipedia.org/wiki/Composition_(combinatorics)
