Average number of random permutations of a sequence, before seeing a sorted sequence Suppose you have a sequence of N numbers. You check the sequence and see if it's sorted in ascending order . If not, you shuffle it (i.e., randomly permute the order of its elements) and check again. How many checks do you need to perform, in average, before seeing a sorted sequence? I believe the answer is N!, and (I think) I have a proof, but I would like to see how you would go around proving it, because I don't think my proof is the most elegant/straightforward.
 A: Let us start by assuming $N$ unique entries in our vector.
The action of randomly shuffling a vector and checking whether it is sorted in a particular order afterwards is equivalent to picking a permutation at random and checking whether it is one very specific one, namely the one that orders the vector in the order we want.
The permutation group of a set with $N$ elements has $N!$ elements. By assumption, each permutation is equally probable.
Your experiment thus is an iterated sampling from a Bernoulli distribution with a success probability of $p=\frac{1}{N!}$. The number of trials until the first success is geometrically distributed, and the expectation you are looking for is the expected number of draws until the first success. Which is the expectation of our geometric distribution, namely $\frac{1}{p}=N!$.
We can extend the treatment for duplicates. Suppose the vector has $n$ unique entries, each one appearing $k_1, k_2, \dots, k_n$ times, so $k_1+k_2+\dots+k_n=N$. Then two permutations of the vector will yield the same vector if they only differ by reorderings within each separate entry. And there are $k_1!k_2!\cdots k_n!$ permutations within each entry. So the overall permutation group of our vector with multiplicities has $\frac{N!}{k_1!k_2!\cdots k_n!}$ permutations that actually result in different vectors. The rest of the analysis runs as above, so the result is that we expect to have to draw $\frac{N!}{k_1!k_2!\cdots k_n!}$ permutations before seeing an ordered vector.
