How many ways can we arrange the letters F, G, H, I and J such that three consecutive letters are in alphabetical order?

Question

Repetition is not allowed. I should also add that the location of the three consecutive letters in the arrangement does not matter. They can be in the beginning, middle or end of the arrangement.

For example, the arrangement G|I|J|F|H is a valid arrangement because G, I, J are in alphabetical order and J|F|G|H|I is also a valid arrangement because G, H and I are in alphabetical order.

I know that the total number of arrangements without consideration of three letters being in alphabetical order is $5!$, but I'm having trouble deriving the arrangements that do follow the restriction from the $5!$.

I'm thinking that maybe I could first select the positions for the three alphabetically sequenced letters and then place the other, but I'm not sure.

Answer 1

Between each consecutive pair of letters in any arrangement, put a $+$ if they are in alphabetical order and $-$ otherwise. This produces a sequence of four signs. We seek the number of arrangements with $++$ somewhere:

• Suppose $++$ appears in the middle, i.e. the middle three letters are in increasing order. There are $\binom53=10$ ways to choose those letters and 2 ways to place the remaining letters, giving 20 arrangements altogether.
• Suppose $++$ is not in the middle. Then the sign sequence either begins with $++-$ or ends with $-++$. There are 3 $++-$ permutation patterns (1243, 1342, 2341) and for each pattern there are 5 choices for the letter not involved in that pattern, giving 15 ways for the $++-$ start case. By symmetry, there are also 15 ways for the $-++$ end case.

This yields $20+15+15=50$ admissible arrangements.

---

The number of permutations of $\{1,\dots,n\}$ with 3 consecutive terms in increasing order is given by OEIS A065429. The complement in the factorials, the number of permutations without this property, is OEIS A049774.