Shelving an Encyclopaedia

All said, there are $26!$ ways to randomly shelve $26$ volumes. If A and B are considered as an immutable pair, like being glued together, the whole of $25$ volumes could be placed randomly in $25!$ ways. Thus the probability of having volumes A and B next to each other in the right order is $\displaystyle \frac{25!}{26!}=\frac{1}{26}.$

Pair AB could be in any of $25$ positions while the remaining $24$ volumes can be permuted arbitrarily, giving the probability of $\displaystyle \frac{25\cdot 24!}{26!}=\frac{1}{26}.$

Employing the reasoning from that in the first solution to the first question, glue volumes A, B, C to obtain a collection of $24$ books. The answer then is $\displaystyle \frac{24!}{26!}=\frac{1}{26\cdot 25}.$

Employing the reasoning from the second solution to the first question, the sequence ABC can be located in any of $24$ places. The other $23$ volumes con be permuted arbitrarily, giving the probability of $\displaystyle \frac{24\cdot 23!}{26!}=\frac{1}{26\cdot 25}.$

Let $A(n)$ denote the set of permutations of $\mathbb{N}_{n+1}=\{1,2\ldots,n,n+1\}$ that do not contain two successive numbers next to each other in the right order, i.e., the permutations with no substrings $k(k+1),$ whatever $k,$ and let $a(n)=|A(n)|$ be the number of elements of $A(n).$ (This is sequence oeis.org/A000255 from the online encyclopedia of integer sequences.) Note that we are looking for the number $(n+1)!-a(n),$ $(n=25)$ of permutations that do contain such pairs of successive numbers.

A permutation $\sigma_{n+1}\in A(n)$ can be associated with a number of permutations from $A(n-1)$ when $n+1$ is excluded. Permutations from $A(n-1),$ with $n$ last can be looked at as members of $A(n-2)$ and $n=1$ can be properly inserted in an of $n-1$ positions, $0,1,\ldots,n-2,$ which produces $(n-1)\cdot a(n-2)$ permutations from $A(n).$ On the other hand, given a permutation from $A(n-1),$ with $n$ in, say, position, $k\ne n,$ the term $n+1$ can be inserted in $n$ positions: $0,1,\ldots,k-1,k+1,\ldots,n,$ leading to the total of $n\cdot a(n-1)$ permutations. Thus we are led to a recurrence relation:

$\begin{align}a(n)&=n\cdot a(n-1)+(n-1)\cdot a(n-2),\\ a(0)&=a(1)=1.\end{align}$

For a verification, note that

$ \begin{align} a(2)&=2\cdot 1+1\cdot 1=3&\text{ and }&(2+1)!-3=3,\\ a(3)&=3\cdot 3+2\cdot 1=11&\text{ and }&(3+1)!-11=13,\\ a(4)&=4\cdot 11+3\cdot 3=53&\text{ and }&(4+1)!-53=67,\\ a(5)&=5\cdot 53+4\cdot 11=309& \text{ and }&(5+1)!-309=411,\\ a(6)&=6\cdot 309+5\cdot 53=2119& \text{ and }&(6+1)!-2119=2921,\\ a(7)&=7\cdot 2119+6\cdot 309=16687& \text{ and }&(7+1)!-16687=23633,\\ \end{align}$

in agreement with the second column of the table in the solution to question 4.

Thus one answer to question 3 is $\displaystyle \frac{n!-a(n-1)}{n!}.$

Given the formula for the number of derangements $d_n$ of $n$ elements, it is straightforward to verify that

$\displaystyle a(n-1)=\frac{d_{n+1}}{n}$

which gives another answer to question 3, $\displaystyle 1-\frac{d_{n+1}}{n\cdot n!}.$

This is a special case of question 4.

To generalize question 2, $k\gt 1$ consecutive volumes appear next to each other in the right order in $(26-k+1)(26-k)!=(27-k)!$ possible placements of the encyclopaedia on a shelf. There are $26-k+1=27-k$ sequences of $k$ successive volumes. The number $(27-k)(27-k)!$ accounts for all possible occurrences of the sequences of $k$ successive volumes. But some of this are counted twice (or more). For example, for $k=3,$ the sequences KLMN contains both subsequences KLM and LMN of length $3.$ This suggests Inclusion/Exclusion approach.

Let $S(k)$ denote the total number of successive sequences of length $k$ in the right order and next to each other. Then

$\displaystyle S(k)=\sum_{j=0}^{26-k}(-1)^j(27-k-j)(27-k-j)!$

Here's programmatic results.

$\begin{array}{ccccccc} n\;\text{\\}\;k&2&3&4&5&6&7\\ ---&---&---&---&---&---&---&\\ 3 &3&1&0&0&0&0\\ 4 &13&3&1&0&0&0\\ 5 &67&14&3&1&0&0\\ 6 &411&77&14&3&1&0\\ 7 &2921&493&78&14&3&1\\ 8 &23633&3624&503&78&14&3 \end{array}$

... to be continued ...

The problem originated on twitter with Vincent Pantaloni's posting of question 1. "Gluing" volumes together is a nice idea suggested by Vincent.

I am grateful to @centristwonk for the reference to oeis.org/A000255 and the formula $\displaystyle \frac{n! - [d(n + 1) / n]}{n!}.$