## How many words (at most 6 letters) formed from a, b, c, d, e, f; Combinatorics

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...

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.