Array sort input

Question

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:

1. The probability that any two of incoming sequence elements are equal, tends to $0$?
2. The probability that the incoming sequence is already sorted, tends to $\frac{1}{n!}$?

Why / why not?

Answer 1

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

2. 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!}$.