Array sort input Suppose that there is an algorithm which sort a sequence of $n$ elements
$$a_1, a_2, ..., a_n$$
Each of the $a_i$ is chosen with probability $1/k$ from a set of $k$ distinct integer numbers. 
Is it true, given that $k \to \infty$, that:


*

*The probability that any two of incoming sequence elements are equal, tends to $0$?

*The probability that the incoming sequence is already sorted, tends to $\frac{1}{n!}$?


Why / why not?

*

*Yes. You have $k^n$ possible tuples. If you are given two tuples, the probability they are the same is $\frac{1}{k^n}$, which goes to 0.

*Yes. As $k\rightarrow \infty$, the probability that two of your numbers are the same goes to 0. So we only need to figure the probability that $n$ distinct numbers are arranged in order, which is $\frac{1}{n!}$.
