Expected value of number of sorted elements in a permutation Consider the obvious algorithm for checking whether a list of integers is sorted: start at the beginning of the
list, and scan along until we first find a successive pair of elements that is out of order. In that case, return
false. If no such pair is found by the time we reach the end of the list, return true.
Our elementary operation is a comparison between two integers.
I'm trying to find the average case running time of this algorithm.
For a permutation with the first $k$ elements sorted and the first $k+1$ unsorted the algorithm must make $k$ comparisons. For each combination of $k+1$ elements out of $n$, there is one in which these $k+1$ elements are sorted. The number of possible permutations of $n$ elements without repetition is $n!$. Therefore the probability that at least the first $k+1$ elements are sorted is: $$\binom{n}{k+1}\cdot\frac{1}{n!}$$
If $K$ is a discrete random variable over the natural numbers 1 to $n-1$ (our event space, since the best case was $k=1$ and the worst case was $k=n-1$), this probability is $\mathbb{P}(K\ge k+1)=\mathbb{P}(K>k) $. 
We have that: $$\mathbb{E}[K]=\sum\limits_{k=1}^{n-1}\mathbb{P}(K>k)$$
We also have that:
$$\sum\limits_{k=0}^{n}\binom{n}{k}=2^n$$
$\binom{n}{0}=1$ for all $n$, so $\sum\limits_{k=1}^{n}\binom{n}{k}=2^n-1$.  Therefore, if $K$ is the distribution of running times of our algorithm:
$$\mathbb{E}[K]=\sum_{k=1}^{n-1}\Bigg[\binom{n}{k+1}\cdot\frac{1}{n!}\Bigg]=\frac{1}{n!}\sum_{k=1}^{n-1}\binom{n}{k+1}=\frac{1}{n!}\sum_{k=2}^{n}\binom{n}{k}=\frac{1}{n!}\Bigg(\sum_{k=1}^{n}\binom{n}{k}-\binom{n}{1}\Bigg)=
$$
$$
=\frac{1}{n!}\Bigg(2^n-1-\frac{n!}{1!(n-1)!}\Bigg)=\frac{2^n-n-1}{n!}
$$
However, this gives nonsensical values. It should be that for all $n<0$ and $n\in\mathbb{N}, \mathbb{E}[K]\ge1$, since the algorithm must check at least the first pair of elements. However, this function for the expected value does not satisfy this.
I can't see where I've gone wrong, but I must have. What have I done incorrectly?
 A: Suppose that the first $k$ elements are sorted, but the first $k+1$ are not. There are $\binom{n}{k+1}$ ways to choose the first $k+1$ elements. They can be permuted in $(k+1)!$ ways, but only $k$ of these permutations have the desired property. The remaining $n-k-1$ elements can be permuted in $(n-k-1)!$ ways, so there are
$$k(n-k-1)!\binom{n}{k+1}=\frac{kn!}{(k+1)!}$$
permutations in which the first $k$ elements are sorted, but the first $k+1$ are not. Thus,
$$\Bbb P(K=k)=\frac{k}{(k+1)!}$$
for $1\le k\le n-2$. For $k=n-1$, however, a small correction is needed: we’ll have $K=n-1$ both when the list is sorted except for the last element and when it’s completely sorted, so 
$$\Bbb P(K=n-1)=\frac{n}{n!}=\frac{n-1}{n!}+\frac1{n!}\;,$$
and
$$\begin{align*}
\Bbb E[K]&=\frac{n-1}{n!}+\sum_{k=1}^{n-1}\frac{k^2}{(k+1)!}\\
&=\frac{n}{n!}-\frac1{n!}+\sum_{k=2}^n\frac{(k-1)^2}{k!}\\
&=\frac1{(n-1)!}-\frac1{n!}+\sum_{k=2}^n\frac{k^2}{k!}-2\sum_{k=2}^n\frac{k}{k!}+\sum_{k=2}^n\frac1{k!}\\
&=\frac1{(n-1)!}+\sum_{k=2}^n\frac{k}{(k-1)!}-2\sum_{k=2}^n\frac1{(k-1)!}+\sum_{k=2}^{n-1}\frac1{k!}\\
&=\sum_{k=1}^{n-1}\frac{k+1}{k!}-2\sum_{k=1}^{n-2}\frac1{k!}+\sum_{k=2}^{n-2}\frac1{k!}\\
&=\sum_{k=1}^{n-1}\frac1{(k-1)!}+\sum_{k=1}^{n-1}\frac1{k!}-\frac2{1!}-\sum_{k=2}^{n-2}\frac1{k!}\\
&=\frac1{0!}+\sum_{k=1}^{n-2}\frac1{k!}+\frac1{1!}+\frac1{(n-1)!}-2\\
&=\sum_{k=1}^{n-1}\frac1{k!}\;.
\end{align*}$$
As a quick and dirty check, for $n=2$ we have $\Bbb E[K]=1$, which is clearly correct, and for $n=3$ we have $\Bbb E[K]=\frac32$, which is easily verified by direct computation: the permutations $123,132$, and $231$ have $K=2$, and the permutations $213,312$, and $321$ have $K=1$.
The sequence $$a_n=n!\sum_{k=1}^{n-1}\frac1{k!}$$ is OEIS A038156 and apparently has the closed form
$$a_n=\lfloor (e-1)n!\rfloor-1\;.$$
A: Regarding the "where did I go wrong?" part of the question:
The formula
$$\binom{n}{k+1}\cdot\frac{1}{n!}$$
is not the probability that the first $k+1$ elements are sorted, as you
can easily confirm by taking any moderately large value of $n$ and a small value of $k$,
such as $n=5$, $k=1$.
The error is that having chosen your first $k+1$ elements, which can appear only
in one way (sorted order), the remaining $n-k-1$ elements can occur in any order.
Each of the resulting permutations of all $n$ elements has probability $\frac{1}{n!}.$
Hence you undercount by a factor of $(n-k-1)!$.
A: For $k=1$ to $n-1$, define the indicator random variable $X_k$ by $X_k=1$ if the first $k$ elements are in sorted order, and by $X_k=0$ otherwise. Then the number $Y$ of comparisons is $X_1+X_2+\cdots+X_{n-1}$. By the linearity of expectation we have
$$E(Y)=E(X_1)+E(X_2)+\cdots+E(X_{n-1}).$$
But $\Pr(X_k=1)=\frac{1}{k!}$, so $E(X_k)=\frac{1}{k!}$, and we are finished. 
