Probability of list having a pair of unchanged consecutive elements once ordered

Question

I've been grading exams for most of the day. Once I finished grading, I started entering the grades into my gradebook -- one by one, from top to bottom on the stack.

About halfway through, I entered one students grade and the next student on the stack was also the next person alphabetically in the gradebook.

What is the probability of this happening with $n$ students, all of whom have unique names?

Equivalent question:

For a random permutation $\left(a_1,a_2,\ldots,a_n\right)$ of the list $\left(1,2,\ldots,n\right)$, what is the probability that there exists at least one entry $k$ of the permutation that is followed immediately by $k+1$ (that is, $k = a_i$ and $k+1 = a_{i+1}$ for some $i \in \left\{1,2,\ldots,n\right\}$) ?

For small $n$, it's not hard to exhaustively calculate the probability. But my combinatorics skills are rusty, and I don't think I can easily calculate this for my 30 students.

Answer 1

This is a good exercise in using the principle of inclusion exclusion, I think I may have even seen it in a combinatorics text.

Given a random permutation $\pi$ of $\{1,2,\dots,n\}$, you want to the find the probability that some $i$ is immediately followed by $i+1$ in $\pi$. For each $i=1,2,\dots,{n-1}$, let $E_i$ be the set of permutations where $i+1$ comes right after $i$, so you want $$\frac{|E_1\cup E_2\cup \dots \cup E_{n-1}|}{n!}.$$ Using PIE, $$ |E_1\cup E_2\cup \dots \cup E_{n-1}|=\sum_{k=1}^{n-1}(-1)^{k+1}\hspace{-.8cm}\sum_{1\le i_1<i_2<\dots<i_k\le n-1} |E_{i_1}\cap E_{i_2}\cap \dots \cap E_{i_k}| $$ We need to find the size of the intersection $|E_{i_1}\cap E_{i_2}\cap \dots E_{i_k}|$. For permutations in $E_{i_1}$, we can think of $i_1$ and $i_1+1$ as being joined together to be a single object. There are then $n-1$ elements to be permuted, so $$|E_{i_1}|=(n-1)!.$$ Similarly, $$|E_{i_1}\cap E_{i_2}|=(n-2)!,$$ since both $i_1$ is joined to $i_1+1$ and $i_2$ to $i_2+1$, so there are only $(n-2)$ objects to permute. At first, it might seem like you need to break into cases based on whether $i_2-i_1=1$ or $i_2-i_1>1$. However, it turns out you get the same answer either way; either there are three objects joined together and $n-3$ singletons, or two pairs joined together and $n-4$ singletons.

Similarly, it miraculously works out that $$|E_{i_1}\cap E_{i_2}\cap \dots \cap E_{i_k}|=(n-k)!.$$ Therefore, all $\binom{n-1}k$ terms in the inner summation are equal to $(n-k)!$, and we have $$ P(\text{some $i$ followed by $i+1$})=\frac1{n!}\sum_{k=1}^{n-1}(-1)^{k+1}\binom{n-1}k(n-k)!=\frac1n\sum_{k=1}^{n-1}\frac{(-1)^{k+1}(n-k)}{k!} $$ As $n\to\infty$, this probability converges to $1-e^{-1}$.

Answer 2

Let $a_n$ be the number of permutations of the list $[1,2,\dots,n-1,n]$ in which at least one entry $i$ is immediately followed by $i+1$. The general term is $$a_n=n!-!n-!(n-1)$$ where $!n$ denotes the subfactorial. This sequence is also in the OEIS.

Answer 3

Restating the problem:

Fix a positive integer $N$. A permutation of length $N$ shall mean an $N$-tuple containing each of the $N$ numbers $1,2,\ldots,N$ exactly once. Such a permutation $\left(a_1,a_2,\ldots,a_N\right)$ is called good if there is at least one $i$ (with $1 \leq i \leq N-1$) such that $a_i + 1 = a_{i+1}$. How to count the number of good permutations?

Example: For $n=3$, the good permutations are $\left(1,2,3\right)$, $\left(2,3,1\right)$ and $\left(3,1,2\right)$.

Call a permutation bad if it is not good and call it ugly if it is good for exactly one index $i$. Let $G(N)$, $B(N)$, $U(N)$ be the number of the good, the bad, and the ugly permutations of length $N$.

Given a bad permutation of length $N$, we obtain a permutation of length $N-1$ by striking $N$ off the sequence. The result is either bad or (if we started from $\ldots, x,N,x+1,\ldots$) it is ugly. In reverse, inserting $N$ anywhere except after the $N-1$ in a bad permutation of length $N-1$ gives a bad permutation of length $N$, and so does inserting $N$ between the only consecutive $x$ and $x+1$ of an ugly permutation of length $N-1$. We conclude that $$\tag1 B(N)=(N-1)B(N-1)+U(N-1).$$

If from an ugly permutation with $x$ followed by $x+1$, we strike the $x+1$ and replace $y$ by $y-1$ for al remaining $y>x$, we end up with a good permutation of length $N-1$ (note that $x+1$ cannot be followed by $x+2$ in the original ugly permutation). In reverse, from a good permutation, we can pick any $x$, replace all $y>x$ with $y+1$ and then insert $x+1$ after the $x$ to end up with an ugly permutation. We conclude that $$\tag2NG(N-1)=U(N) $$ From $(1)$ and $(2)$ and $B(N)+G(N)=N!$, $$\begin{align}B(N)&=(N-1)B(N-1)+(N-1)G(N-2)\\&=(N-1)B(N-1)+(N-1)!-(N-1)B(N-2).\end{align} $$