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

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.

• The number of good permutations is equal to $n!$ minus the number of "bad permutations" (where bad permutations are those which are not good, i.e. there exists no $i$ for which $a_i+1=a_{i+1}$). – Dave Jun 20 at 13:37
• Can you tell me the number of bad permutations ? @Dave – Firex Firexo Jun 20 at 13:50
• – Gerry Myerson Jul 1 at 22:37

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

• This is either very similar to, or exactly the same, as the number of derangements (or its complement). Is there a different proof that maps this problem to counting derangements? – antkam Apr 30 at 23:45
• Hmm, so letting $L_n$ be the number of permutations of $\{1,2,\dots,n\}$ with no $i+1$ after $i$, then $L_n=\frac1n D_{n+1}$. I do not know of a bijective proof, but I am curious... @antkam – Mike Earnest May 1 at 0:02
• Thanks! I think it's time for me to brush up on my combinatorics -- I know I could've figured this out a few years ago. – Logan Clark May 1 at 0:17
• @antkam And also it is true that $L_n=nD_{n-1}+(n-1)D_{n-2}$. – Mike Earnest May 1 at 0:29
• Just a follow up, no need to answer if you don't feel like it. How does this change if we allow repeated names? Or numbers, as is the case in your solution. – Logan Clark May 1 at 1:58

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}

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.

• Also, $a_n=n!-\frac{!(n+1)}{n}$. – Mike Earnest Jun 20 at 15:50