Counting words with letter counts of specific parity Question: How many words of length $ n $ are there consisting of letters $ A $, $ B $, $ C $ such that:


*

*At least one letter occurs an even (possibly zero) number of times

*At least one letter occurs an odd number of times


By writing a simple Python script verifying all possible $ \{A, B, C\}\text{*} $ words of length $ n $, I got the following sequence:
3, 6, 21, 60, 183, 546, 1641, 4920, 14763

Which led me to OEIS sequence A054878. In the formula section there is a neat recurrence relation:
$$ a_{n} = 2a_{n-1} + 3a_{n-2} $$
The $ 3a_{n-2} $ part is clear to me, as we count these words like so:
$$ \underbrace{AA\underbrace{XX...XX}_{\text{n - 2}}}_{\text{n}} + \underbrace{BB\underbrace{XX...XX}_{\text{n - 2}}}_{\text{n}} + \underbrace{CC\underbrace{XX...XX}_{\text{n - 2}}}_{\text{n}}$$
Since adding two of the same letter doesn't impact parity. But what about the $ 2a_{n-1} $ part? Or maybe there is an easier way to solve the problem?
 A: There are only two possibilities for any such sequence length $n$:


*

*There are $2$ letters that occur an odd number of times and $1$ letter an even number of times $(o,o,e)$.

*There are $2$ letters that occur an even number of times and $1$ letter an odd number of times $(o,e,e)$.


If $a_{(o,o,e)}(n)$ is the number of sequences of the first type and $a_{(o,e,e)}(n)$ is the number of sequences of the second type then the number of desired sequences $a(n)$ is:
$$a(n)=a_{(o,o,e)}(n)+a_{(o,e,e)}(n)\tag{1}$$
Then each of these have individual recurrences. For the first term on the right hand side of $(1)$:
$$a_{(o,o,e)}(n)=2a_{(o,e,e)}(n-1)+3a_{(o,o,e)}(n-2)\tag{2i}$$ 
Since a sequence of type $(o,o,e)$ either ends with an "odd" letter $o$ ($2$ possibilities) then the remaining sequence is of type $(o,e,e)$, this accounts for the first term. 
The sequences of type $(o,o,e)$ ends with an "even" letter in two ways: two "evens" $ee$ ($1$ possibility) then the remaining sequence is of type $(o,o,e)$, or ends with "odd" and "even" letters $oe$ ($2$ possibilities) then the remaining sequence is of type $(o,o,e)$, this accounts for the second term.
We can reason similarly for the second term on the right hand side of $(1)$:
$$a_{(o,e,e)}(n)=2a_{(o,o,e)}(n-1)+3a_{(o,e,e)}(n-2)\tag{2ii}$$
Since a sequence of type $(o,e,e)$ either ends with an "even" letter $e$ ($2$ possibilities) then the remaining sequence is of type $(o,o,e)$, this accounts for the first term.
The sequences of type $(o,e,e)$ ends with an odd letter in two ways: two "odds" $oo$ (1 possibility) then the remaining sequence is of type $(o,e,e)$, or ends with "even" and "odd" letters $eo$ ($2$ possibilities) then the remaining sequence is of type $(o,e,e)$, this accounts for the second term.
So, using $(2\text{i})$ and $(2\text{ii})$ in $(1)$ we get:
$$\begin{align}a(n)&=a_{(o,o,e)}(n)+a_{(o,e,e)}(n)\\
&=2(a_{(o,e,e)}(n-1)+a_{(o,o,e)}(n-1))+3(a_{(o,o,e)}(n-1)+a_{(o,e,e)}(n-2))\\
&=2a(n-1)+3a(n-2)\end{align}$$
A: Given a word of length $n-1$, you always have only 2 possible letters to append in order to create a legit word of length $n$. 
It's not very elegant, but you can break it into cases:

*If the word has 2 letters that appear odd number of times, then only they can be appended. (else you'll have word where all characters appear odd number of times)

*If the word has 2 letters that appear even number of times, then it's the same has above. (else you'll have word where all characters appear even number of times)

Edit: You don't count words twice because when you take word of length $n-2$ and append $AA$, $BB$ or $CC$ you don't change the parity of the letters, whereas when you add one of the letters in the other case, you do change the letter's parity.
