3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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}$). $\endgroup$ – Dave Jun 20 at 13:37
  • $\begingroup$ Can you tell me the number of bad permutations ? @Dave $\endgroup$ – Firex Firexo Jun 20 at 13:50
  • $\begingroup$ See also math.stackexchange.com/questions/2760360/… $\endgroup$ – Gerry Myerson Jul 1 at 22:37
2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – antkam Apr 30 at 23:45
  • $\begingroup$ 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 $\endgroup$ – Mike Earnest May 1 at 0:02
  • $\begingroup$ 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. $\endgroup$ – Logan Clark May 1 at 0:17
  • 1
    $\begingroup$ @antkam And also it is true that $L_n=nD_{n-1}+(n-1)D_{n-2}$. $\endgroup$ – Mike Earnest May 1 at 0:29
  • $\begingroup$ 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. $\endgroup$ – Logan Clark May 1 at 1:58
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.