AFHKNW

Relevant wiki: Permutations - Problem Solving

Think of a string of 27 boxes, one empty, followed by the letters of the alphabet: $\begin{array}{|c|c|c|c|c|c|}\hline \\ \ \ \ & \mathbf A & \mathbf B & \mathbf C & \cdots & \mathbf Z \\ \hline \end{array}$

Underneath we must place 6 pairs of boxes like this: $\begin{array}{|c|c|}\hline \\ \ \ \ & \star \\ \hline \end{array}$ and 15 empty boxes.

The stars represent the six letters we pick. The empty boxes to the left of the stars provide the "padding" needed to ensure that no two adjacent letters are chosen.

Thus the answer is: in how many ways can we arrange the 6 identical pairs and the 15 identical empty boxes? The answer is $\binom{21}{6} = \frac{21\cdot 20\cdot 19 \cdot 18\cdot 17\cdot 16}{6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1} = 21\cdot 19 \cdot 17\cdot 8 = \boxed{54\,264}.$

Inspiration

I thought of this problem after buying in a second-hand book store six volumes of Sue Grafton's alphabet mysteries. The store happened to have these six: "A" is for Alibi , "F" is for Fugitive , "H" is for Homicide , "K" is for Killer , "N" is for Noose , and "W" is for Wasted . I realized that none of the books were adjacent in the series. "What are the chances of that?" I thought immediately.

I calculated the $54\,264$ arrangements in my head on the way home, but calculating the odds is better done with a calculator around. The probability that six randomly chosen letters from the alphabet contain no adjacent letters is $\frac{\binom{21}{6}}{\binom{26}{6}} = \frac{21\cdot 19\cdot 17\cdot 8}{13\cdot 5\cdot 23\cdot 22\cdot 7} = \frac{54264}{230230};$ or reduced further, $= \frac{3\cdot 19\cdot 17\cdot 4}{13\cdot 5\cdot 23\cdot 11} = \frac{3876}{16445} \approx 23.6\%.$

Incidentally, at this time, Grafton has not yet written "Z" is for ... , and "Y" is for Yesterday appeared so recently that one cannot reasonable expect it in a second-hand book store. This makes the odds slightly lower, about 20.2%.

Relevant wiki: Permutations - Problem Solving

Imagine putting 20 identical objects in a straight line, and then adding 6 objects of another type between them. Now you have a line of 26 objects, 6 of them different from the rest. Apply the alphabet to this line of objects, and imagine that the 6 “distinct” objects highlight 6 letters in the matching position. This is your “answer set”. Notice how the way you place these 6 objects into the rest determines the letters in the answer set, each unique way representing an unique solution. So now the problem becomes “how to place 6 objects between 20 other objects?” The solution is apparent: There are 21 spaces for 6 objects, so the answer is

$21 \choose 6$ $=\boxed{54264}$

• Let me mean the letters $A$ , $B$ , $C, \ldots \ldots \ldots, Z$ by the integers $1,2.3, \ldots \ldots \ldots, 26$ , respectively.

-So, now the problem is equivalent to finding the number of ways to choose $6$ integers from the first $26$ integers so that no two chosen integers are consecutive integers.

• Let $a, b, c, x, y, z$ be six integers (in increasing order).

• Note that, even when any two of $a, b, c, x, y, z$ are consecutive, no two of $a, b+1, c+2, x+3, y+4, z+5$ are consecutive.

• That means, we can choose any six integers $a, b, c, x, y, z$ from the set of $\{1, 2, 3, \ldots \ldots \ldots, {\color{#3D99F6} \boxed{21}}\}$ , then choose the letters represented by $a, b+1, c+2, x+3, y+4, z+5$ .

Hence the number of ways is: $\binom{21}{6}= \boxed{54264}$ .

The following is a more empirical approach that derives a formula for any set of k different non-adjacent items (a $k$ -set) from an ordered collection that contains $n$ items (a $n$ -collection). By experimentally checking the combinations of 2 different non-adjacent letters, you can quickly induce that each new letter $n$ increases the number of possible combinations by $n-2$ . That is, when you have a 4-collection, you have 3 2-sets. When you increase the number of letters to 5, you get $3+(5-2)=6$ 2-sets. When you consider 3-sets, each new letter that you add, can be added to a set that contains any letter, except: 1) itself; 2) it's adjacent letter(n-1). That means that it will generate a new set with any $(k-1)$ -set of a $(n-2)$ -collection. For example, a 5-collection contains 1 3-set. A 6-collection will contain the same set AND any new sets generated by the new letter. In that case that means that it will generate 1 + the number of 2-sets of a 4-collection. So the number of 3-sets in a 6-collection is $1 + 3 = 4$ .

Now we can generalize a formula:

$N(k$ -sets $/n$ -collection $) = N((k-1)$ -sets $/(n-2)$ -collection $) + N((k$ -sets $)/(n-1)$ -collection)

Where $N(x)$ means number of $x$ , and $k$ -sets $/n$ -collection means k-sets from an n-collection.

The answer is 54264.
I wrote a little program for Liberty Basik to find the answer.
Initially the program was generating the combinations and was able to print them if I wanted to. Then I minimized it only to count the number of combinations.
First: Let's use numbers from 1 to 26 instead of letters from A to Z.
Second: Let's use the variable "Distance" so that Distance = 1 means no restrictions for adjacent numbers.
This would be the case for the full number of combinations, which is (26.25.24.23.22.21) / (1.2.3.4.5.6) = 230230.
Our task is to make Distance = 2 (to skip one position and avoid adjacent numbers).
This universal approach prompted me to do a small research and find all the answers
for Distances from 1 to 5 (5 by the way is the maximal distance possible).
Here are the results:
Distance=1 - 230230 combinations with adjacent numbers like 123456, 123457, 123458, ... , 21,22,23,24,25,26;
Distance=2 - 54264 combinations with no adjacent numbers like 1,3,5,7,9,11, ... , 16,18,20,22,24,26;
And now even stronger restrictions Distance=3 - 8008 combinations like 1,4,7,10,13,15, ... , 11,14,17,20,23,26;
Distance=4 - 462 combinations like 1,5,9,13,17,21, ... 6,10,14,18,22,26;
Distance=5 - 1 combination which should be 1,6,11,16,21,26.

And here is the minimized program:

 for Distance = 1 to 5  
  print Distance;" - ";  
 Counter = 0  
   for a = 1 to 26  
    for b = a + Distance to 26  
     for c = b + Distance to 26  
      for d = c + Distance to 26  
       for e = d + Distance to 26  
        for f = e + Distance to 26  
 Counter = Counter + 1  
        next f  
       next e  
      next d  
     next c  
    next b  
   next a  
  print Counter  
 next Distance

We will construct a solution by stepwise selecting the (alphabetically) next letter. The first letter cannot come after P, because the alphabetically last solution is $\{P,R,T,V,X,Z \}$ . So there are 16 choices for the first letter. When the $i$ th letter $l_i$ has been selected, then the next letter comes at least two places after $l_i$ and comes before the $(14+2i)$ th position. This yields the following expression: $\sum_{l_1=1}^{16} \sum_{l_2=l_1+2}^{18} \sum_{l_3=l_2+2}^{20} \sum_{l_4=l_3+2}^{22} \sum_{l_5=l_4+2}^{24} \sum_{l_6=l_5+2}^{26} 1.$ This sums up to $\boxed{54264}$ .

A rude brute force way to find it out in Python :-)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

max = 26

def getRange(i, start):
  return range(start, max - 2*(5-i) + 1)

count = 0
for i1 in getRange(0, 1):
  for i2 in getRange(1, i1+2):
    for i3 in getRange(2, i2+2):
      for i4 in getRange(3, i3+2):
        for i5 in getRange(4, i4+2):
          for i6 in getRange(5, i5+2):
            count += 1
print(count)

### result: 54264

Let there be a row of 21 identical objects. Select 6 of them, then insert 5 more between adjacent pairs to ensure that none of the six are adjacent. Overlay the alphabet onto the row of 26 objects.

There are 21C6 ways of doing this, each of which corresponds to one set of valid letters.