Finding a recurrence relation in combinatorics

Question

First, my English is not that good so please don't laugh. I need to find a recurrence relation for : The number of words with the length of n that could be composed from the letters A,B,C,D, so the words won't include the combinations "AB","BA","AD" or "BC".

My thinking was to look at the beginning of a word. if it starts with C or D then the continuation has A(n-1) combinations (= A with index n-1). So for the beginning of B or D i get a total of 2*A(n-1). But if the word starts with A, there could be only C or A after this letter. if it's C we continue regularly and say the continuation has A(n-2) combinations. But if there is an A after the A, we have the same situation repeats and repeats until the last letter. so we get for this : A(n-2)+A(n-3)+...+A1

If the word starts with B we get the same combinations as it starts with A so again : A(n-2)+A(n-3)+...+A1

Summing everything gives me the series : An = 2*[A(n-2)+A(n-3)+...+A1] + 2*[A(n-1)] with a1 = 4 , a2 = 12

BUT I wrote a software to bruteforce calculating this thing and realized that the solution is actually the same but adding A1. like this : An = 2*[A(n-2)+A(n-3)+...+A1] + 2*[A(n-1)] + A1 with a1 = 4 , a2 = 12

The series actually starts like this : 4, 12 36, 108, ...

Can someone please tell me where is my mistake and why I don't have this A1 in my solution ? Thanks a lot.

Answer 1

The additional number you need to add at the end of $2A_{n-1}+2A_{n-2}+\cdots+2A_2+2A_1$ is $4$ for the patterns not captured by your recursions, namely "AAA...AAA", "AAA...AAC", "BBB...BBB", "BBB...BBD". Coincidentally this is the same as $A_1$.

There is a much simpler recurrence: $A_n = 3 A_{n-1}$, which can easily be solved as $A_n = 4\times 3^{n-1}$.

Any $n$-letter word can be made up of an $n-1$-letter word followed by a particular letter. But for A at the end you cannot have "...BA"; for B at the end you cannot have "...AB"; for C you cannot have "...BC"; for D you cannot have "...AD". So the particular letter at the end can follow three possible letters at the end of the $n-1$-letter word (but not the fourth). And there is one $1$-letter word of each type. So there are $3^{n-1}$ $n$-letter words ending with each particular letter.

Answer 2

If it starts with $B,$ you can't have an $A$ next, so there aren't $A(n-1)$ combinations. I would let $a(n)$ be the number of words starting with $A$, similarly $b(n),c(n),d(n)$ and let $e(n)=a(n)+b(n)+c(n)+d(n)$ which is what you want. Now do what you were trying: write relations like $d(n)=e(n-1)$ because if you start with $D$ you can follow with anything. The separate names let you keep track of the relations between the letters. As $A$ can only be followed by $A$ or $C$, you have $a(n)=$ what?

Answer 3

The first letter can be anything. Let $W(n)$ be the number of allowable words of length $n$. $W(1) = 4.$

The second letter depends on what the first letter was, so let's rewrite

$$W(n) = W_A(n) + W_B(n) + W_C(n) + W_D(n),$$ where $W_X(n)$ are the number of words of length $n$ that end in letter $X = A, B, C, D.$

So $W_A(1) = W_B(1) = W_C(1) = W_D(1) = 1.$

If the first letter is $A$, then the second letter can be $A$ or $C$, so $W_A(2) = 2.$

If the first letter is $B$, then the second letter can be $B$ or $D$, so $W_B(2) = 2.$

If the first letter is $C$, then the second letter can be anything, so $W_C(2) = 4.$

If the first letter is $D$, then the second letter can be anything, so $W_D(2) = 4.$

Hence $W(2) = 12.$ Repeating, $W(3) = 4 + 4 + 16 + 16 = 40,$ and $W(4) = 8 + 8 + 64 + 64 = 144.$

Looking at the form, we can see the formula for $W(n) = 2^n + 2^{2n-1}.$

So, $W(n+1) = 2^{n+1} + 2^{2n+1}$, and

$$W(n+1) = \frac{2^{n+1} + 2^{2n+1}}{2^n + 2^{2n-1}} W(n), W(1) = 4.$$

Answer 4

Since the words do not include the combinations "AB","BA","AD" or "BC" which end with each of $A$, $B$, $C$, $D$ exactly once, a good point of view is to write the words from right to left.

There are four choices for the first letter (on the right) and then three choices for each subsequent letter because exactly one letter is forbidden at each step.

This gives $4\cdot 3^{n-1}$.

Answer 5

Denote by $a(n)$ the number of admissible words ending in A, and similarly for B, C, and D. Then $$\bigl(a(1),b(1),c(1),d(1)\bigr)=(1,1,1,1)$$ and $$\left[\matrix{a(n+1)\cr b(n+1)\cr c(n+1)\cr d(n+1)\cr}\right]= \left[\matrix{1&0&1&1\cr 0&1&1&1\cr 1&0&1&1\cr 0&1&1&1\cr}\right] \left[\matrix{a(n)\cr b(n)\cr c(n)\cr d(n)\cr}\right]\qquad(n\geq1)\ .$$ It turns out that the vector $(1,1,1,1)$ is an eigenvector of the $4\times4$-matrix $M$ appearing here, and the corresponding eigenvalue is $3$. It follows that $$\bigl(a(n),b(n),c(n),d(n)\bigr)=3^{n-1}(1,1,1,1)\qquad(n\geq1)\ .$$