Expected number of permutations required to sort a list of numbers

Question

Given a list of N numbers if we are performing random permutations each time and checking whether the list is sorted, what will be the expected number of permutations required to sort that list?

Answer 1

As it happens, probability of sorted array with duplicate numbers was asked just a few hours ago. If number $x_j$ is present $n_j$ times, with $1\le j\le k$ and $\sum_jn_j=n$, the probability for a uniformly randomly chosen permutation to order the list is

$$ \frac{\prod_jn_j!}{n!}\;, $$

so the expected number of permutations required is

$$ \frac{n!}{\prod_jn_j!}=\binom n{n_1,\ldots,n_k}\;, $$

the number of distinguishable arrangements of the numbers.