Counting words with letter counts of specific parity

Question

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?

Answer 1

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}$$

Answer 2

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.