Let $a_n$ be the number of words of length $n$ from the alphabet $\{A,B,C,D,E,F\}$ in which $A$ appears an even number of times and $B$ appears an odd number of times. Using generating functions I was able to prove that $$a_n=\frac{6^n-2^n}{4}\;.$$
I was wondering if the above answer is correct and in that case what could be a combinatorial proof of that formula?
On
There's a combinatorial method (by the way, I consider generating functions to be a combinatorial method, but never mind) using inclusion-exclusion. Count the total number of $n$-letter words, subtract off the ones with an odd number of $A$, subtract off the ones with an even number of $B$, then add back in the ones with both an odd number of $A$ and an even number of $B$. Of course, you have to work out the details....
On
I don’t know whether you’d call them combinatorial, but here are two completely elementary arguments of a kind that I’ve presented in a sophomore-level discrete math course. Added: Neither, of course, is as nice as Didier’s, which I’d not seen when I posted this.
Let $b_n$ be the number of words of length $n$ with an odd number of $A$’s and an odd number of $B$’s, $c_n$ the number of words of length $n$ with an even number of $A$’s and an even number of $B$’s, and $d_n$ the number of words of length $n$ with an odd number of $A$’s and an even number of $B$’s. Then
$$a_{n+1}=4a_n+b_n+c_n\;.\tag{1}$$
Clearly $a_n=d_n$: interchanging $A$’s and $B$’s gives a bijection between the two types of word. $(1)$ therefore reduces to
$$a_{n+1}=4a_n+b_n+c_n\;.\tag{2}$$
But $6^n=a_n+b_n+c_n+d_n=b_n+c_n+2a_n$, so $b_n+c_n=6^n-2a_n$, and $(2)$ becomes $$a_{n+1}=2a_n+6^n,a_0=0\;.\tag{3}$$ $(3)$ can be solved by brute force:
$$\begin{align*} a_n&=2a_{n-1}+6^{n-1}\\ &=2(2a_{n-2}+6^{n-2})+6^{n-1}\\ &=2^2a_{n-2}+2\cdot 6^{n-2}+6^{n-1}\\ &=2^2(2a_{n-3}+6^{n-3})+2\cdot 6^{n-2}+6^{n-1}\\ &=2^3a_{n-3}+2^2\cdot 6^{n-3}+2\cdot 6^{n-2}+6^{n-1}\\ &\;\vdots\\ &=2^na_0+\sum_{k=0}^{n-1}2^k6^{n-1-k}\\ &=6^{n-1}\sum_{k=0}^{n-1}\left(\frac13\right)^k\\ &=6^{n-1}\frac{1-(1/3)^n}{2/3}\\ &=\frac{2^{n-1}3^n-2^{n-1}}{2}\\ &=\frac{6^n-2^n}4\;. \end{align*}$$
Alternatively, with perhaps just a little more cleverness $(1)$ can be expanded to
$$\begin{align*} a_{n+1}&=4a_n+b_n+c_n\\ b_{n+1}&=4b_n+2a_n\\ c_{n+1}&=4c_n+2a_n\;, \end{align*}\tag{4}$$
whence
$$\begin{align*}a_{n+1}&=4a_n+4b_{n-1}+2a_{n-1}+4c_{n-1}+2a_{n-1}\\ &=4a_n+4a_{n-1}+4(b_{n-1}+c_{n-1})\\ &=4a_n+4a_{n-1}+4(a_n-4a_{n-1})\\ &=8a_n-12a_{n-2}\;. \end{align*}$$
This straightforward homogeneous linear recurrence (with initial conditions $a_0=0,a_1=1$) immediately yields the desired result.
On
First regard words that contain at least an $A$ or a $C$ and at least a $B$ or a $D$.
Now use the functions "convert the first letter that is $A$ or $C$ in the other one of the two" and "convert the first letter that is $B$ or $D$ in the other one of the two".
These two functions are clearly bijections and commute, so for these words exactly a fourth has the desired property.
Secondly, regard words that either do not contain $A$ or $C$ or do not contain $B$ or $D$, but not both properties are true.
Words that do not contain a $B$ or a $D$ will not contain an odd number of $B$s.
Words that do not contain an $A$ or a $C$ automatically contain an even number of $A$s and the second function above shows bijectively that half of the words work.
Together, again a fourth of all the words have the desired property.
Finally, regard words that do not contain $A$,$B$,$C$,$D$. There are $2^n$ of them.
They do not have an odd number of $B$s.
So, in summary, we take all words $6^n$, divide by four, but we have to subtract the contribution $2^n/4$ of the last case, which gives the formula $$(6^n-2^n)/4.$$
Call $s_n$ the number of words with numbers of A and B of the same parity, and $d_n$ the number of words with numbers of A or B of different parities. Since there are as many words with an odd number of A and an even number of B than words with an even number of A and an odd number of B, one is after $a_n=\frac12d_n$.
Obviously, $s_n+d_n$ is the total number of words of length $n$, that is, $s_n+d_n=6^n$.
On the other hand, adding A or B to a word of length $n$ produces a word of the other type, and adding C, D, E or F produces a word of the same type, hence $s_{n+1}=4s_n+2d_n$ and $d_{n+1}=4d_n+2s_n$.
This yields $s_{n+1}-d_{n+1}=2(s_n-d_n)$. Since $s_1=4$ and $d_1=2$, $s_n-d_n=2^{n}$.
Finally, $a_n=\frac12d_n=\frac14(s_n+d_n)-\frac14(s_n-d_n)=\frac14(6^n-2^n)$.
Edit Here is an alternative proof of the relation $s_n-d_n=2^{n}$, based on the probabilistic method.
Draw uniformly at random a word from the $6^n$ words of length $n$ and let $X_k=-1$ if the $k$th letter is A or B and $X_k=+1$ otherwise. The random variables $(X_k)_{1\leqslant k\leqslant n}$ are independent, $X_k=-1$ with probability $\frac13$, $X_k=+1$ with probability $\frac23$, hence $\mathrm E(X_k)=1-2\frac13=\frac13=x$.
Let $Y_n=X_1X_2\cdots X_n$. Then $Y_n=+1$ if the word contains numbers of A and B of the same parity and $Y_n=-1$ otherwise, thus $6^n\mathrm P(Y_n=+1)=s_n$ and $6^n\mathrm P(Y_n=-1)=d_n$. The independence of the random variables $(X_k)_{1\leqslant k\leqslant n}$ implies that $\mathrm E(Y_n)=\mathrm E(X_1)\mathrm E(X_2)\cdots \mathrm E(X_n)=x^n$, hence $$ s_n-d_n=6^n\mathrm E(Y_n)=6^nx^n=2^n. $$ This also proves that, for the same problem using an alphabet of $\color{red}{N\geqslant4}$ letters, $x=1-\frac4N$ hence $$ \color{red}{a_n=\frac{N^n-(N-4)^n}4}. $$ This formula suggests that a proof by inclusion-exclusion might be available, which would yield the successive powers of $4$ in the binomial expansion of $(N-4)^n$.