Counting words with parity restrictions on the letters 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?

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....
