Hello,

I came across a combinatorics problem I could not solve. The statement is the following:

How many words of at most six letters can you form using letters a, b, c, d, e or f such that no consecutive letters in a word are consecutive in the alphabet (for example, the words ab, cb, adecf, acedf are not possible, but the words ac, da, cad are possible). A letter can not appear in a word more than once.

The only "shortcut" I see in the problem, rather than using plain brute force, is to exploit the symmetry in that the letter a and f have the same "nature", b and e have the same "nature", and letters c and d have the same "natures".

I proceeded in pretty much listing all words, using a slightly faster method than plain brute force, finding the number of words using 1, 2, 3, 4, 5 and 6 letters, and starting with a, b or c. I multiplied the total by 2 and got a not-very-interesting 380 words total.

1. My method seems tedious and stupid; there surely is a better method.
2. My method is not généralisable. How to count the number of words if we're allowed to use more letters than the first 6 of the alphabet?
3. I didn't have the patience to list the words more than once... maybe I made some mistake while counting. By the way, some of my friends also tried the problem and all of them arrived to different numbers...

Thank you in advance,
Bélisaire

Here is a slightly more elaborated version of my solution; 380 words.

Number of words with m letters and starting with letter n:
(1,a)=1
(1,b)=1
(1,c)=1
(2,a)=4
(2,b)=3
(2,c)=3
(3,a)=9
(3,b)=7
(3,c)=8
(4,a)=14
(4,b)=15
(4,c)=15
(5,a)=17
(5,b)=23
(5,c)=23
(6,a)=12
(6,b)=15
(6,c)=19

Using symmetry, as explained above, we get 6 words of 1 letter, 20 words of 2 letters, 48 words of 3 letters, 88 words of 4 letters, 125 words of 5 letters and 92 words of 6 letters, for a big total of 380 words.