Number of words with 8 letters using an alphabet of 3 consonants and 2 vowels with constraints

Question

A new language is developed such that it has $5$ letters $A ,B, C ,D, E$ where A, E are called vowels while B, C, D are called consonants . The language has the following rules :a letter cannot be repeated twice in a row (e.g the sequence $BB$ is not allowed) and a vowel cannot be repeated in a row (the sequence $AE$ or $EA$ of letters is not allowed) . Find the number of all possible eight letter words which begin with a consonants.

Background info:

This is a question that came up in the third round of the $2023$ Kenya mathematics Olympiad and the best student could only score $1$ of the possible ten marks in the question. I tried various methods but could only arrive at $20340$ as the solution by listing all possible permutations of consonants and vowels i.e (cvcvcvcv ,cccccccc and so on) and then counted the number of words for each case.I am unsure if this is even the correct answer.

Answer 1

Recurrence approach. Let $c(n)$ be the number of legal words such that the $n$-th letter is a consonant and let $v(n)$ be the number of legal words such that the $n$-th letter is a vowel. Then the following recurrences hold (why?): for any $n\geq 1$, $$\begin{cases} c(n+1)=2\cdot c(n)+3\cdot v(n)\\ v(n+1)=2\cdot c(n)+0\cdot v(n) \end{cases}$$ or in matrix form $$\left[\begin{matrix} c(n+1)\\v(n+1)\\ \end{matrix}\right]=\left[\begin{matrix} 2 & 3\\ 2 & 0\\ \end{matrix}\right]\left[\begin{matrix} c(n)\\v(n)\\ \end{matrix}\right].$$ In our case, starting with a consonant, we have that $c(1)=3$, $v(1)=0$ and therefore $$\begin{array}{r|cc} n&1&2&3&4&5&6&7&8\\ \hline c(n)&3&6&30&96&372&1320&4872&17664\\ \hline v(n)&0&6&12&60&192&744&2640&9744 \end{array}$$ Hence, the total number of 8 letter words is $c(8)+v(8)=17664+9744=\boxed{27408}$.

Answer 2

I think your approach is fine. First just strings of c's v's, and separating those with v's at the end of the word and those with no v at the end.

0 v's -- $1$
1 v not ending in v -- $6$
1 v ending in v -- $1$
2 v's not ending in v -- ${5\choose 2}$
2 v's ending in v -- ${5\choose 1}$
3 v's not ending in v -- ${4\choose 3}$
3 v's ending in v -- ${4\choose 2}$
4 v's ending in v -- ${3\choose 3}$

At the start of a word and after every v there are 3 choices for c. Otherwise, there are 2 choices for c. There are 2 choices for v.

${7\choose 0}(3)2^7 + {6\choose 1}(3^2)(2^6) + {6\choose 0}(3)(2^7) + {5\choose 2}(3^3)(2^5) + {5\choose 1}(3^2)(2^6)+ {4\choose 3}(3^4)(2^4)+{4\choose 2}(3^3)(2^5)+{3\choose 3}(3^4)(2^4)\\ ({7\choose 0}+{6\choose 0}) (3)2^7 + ({6\choose 1}+{5\choose 1}) (3^2)(2^6) + ({5\choose 2}+{4\choose 2}) (3^3)(2^5) + ({4\choose 3}+{3\choose 3}) (3^4)(2^4)\\ 27408$

Answer 3

The number 20340 seems to be wrong.

Algoritmically: Build tuples of 1...5, select first odd, deselect any word with a pair product of 8,
select all adjacent pairs different,

In Mathematica e.g.

 wordlist = Sort[Tuples[Join[v = {2, 4}, c = {1, 3, 5}], 8]];
   pairs[x_] := Join[Partition[x, 2], Partition[Rest[x], 2]]

  w = Select[wordlist,
     Function[word, OddQ[First[word]] &&
          FreeQ[Times @@@ pairs[word], 8] &&
           And @@ (Unequal[#1, #2] &) @@@ pairs[word] &)];


 Length[w]
   27408

ww = StringJoin @@@ (w /. {1 -> "c", 2 -> "a", 3 -> "p", 4 -> "u",   5 -> "t"})

 Array[Symbol@ww[[RandomInteger[27408]]] &, {24}]

cuputpat, ctcpacpu, ctutatcu, tupcpcut, cactpupc, ptupupuc, tacpcatc,tucupuca, tcuctcat, cucptpuc, ptptctup, ctpucpcp, cutcuctc, tatcupac, capcptcu, tacptcap, tutatcpc, ptctucac, tpcptutu, catacpap, tapapcpu, pcucapup, cupctact, cpatutuc

Probably, for a romanic language one should exclude more than two consonants.

Mathematically challenging: replace the selection And-product by its nested product of combination coefficients.