Lexicographical Neighbours

Taking three different letters from the $26$ letters of the alphabet, character strings of length three can be formed.
Examples are ‘abc’, ‘hat’ and ‘zyx’.
When we study these three examples we see that for ‘abc’ two characters come lexicographically after its neighbour to the left.
For ‘hat’ there is exactly one character that comes lexicographically after its neighbour to the left. For ‘zyx’ there are zero characters that come lexicographically after its neighbour to the left.
In all there are $10400$ strings of length $3$ for which exactly one character comes lexicographically after its neighbour to the left.
We now consider strings of $n \le 26$ different characters from the alphabet.
For every $n$, $p(n)$ is the number of strings of length $n$ for which exactly one character comes lexicographically after its neighbour to the left.
What is the maximum value of $p(n)$?

First, let’s note a couple of things:

1. A string where only one character comes lexicographically after its neighbour to the left is basically a string where all but two characters are in descending order and the exception is one pair of characters that are in ascending order.
2. The number of such strings for a given $n$ is equal to the number of ways to choose two of $n$ places (for the pair of ascending characters), times the number of ways to arrange $n$ characters into those places (i.e., $n$ factorial).

With this in mind, we can create a simple formula for $p(n)$:

$ p(n) = \binom{n}{2} * n! $

That’s the number of ways to choose two places times the number of ways to arrange n characters.

This function increases as n increases up to 26, so the maximum occurs when n = 26. There are many rapid increases in the function—especially near 26 (For instance, at 25 it’s 25 times larger than at 24). Therefore the maximum should be at the highest possible n, and since n ≤ 26, this means n = 26.

Therefore:

$ p(26) = \binom{26}{2} * 26! $

Now let’s calculate this value.

The binomial coefficient is calculated using the formula of n choose k which is n! / [(n-k)! * k!]:

$ \binom{26}{2} = \frac{26!}{(26-2)! * 2!} = \frac{26 * 25}{2} = 325 $

So the maximum value of $ p(n) $ is $ 325 * 26! $.

Therefore, the maximum value is the number of ways to pick 2 spots from 26 (which is 325) times the number of ways to arrange 26 letters (which is 26 factorial). This is a very large number, specifically 103312881775405620205625000000.

More Answers: