$n$-words from the alphabet $A=\{0, 1, 2, 3\}$. How many of them have an even number of zeros and ones? Consider all $n$-words from the alphabet $A=\{0, 1, 2, 3\}$. How many of them have an even number of zeros and ones?
I showed that the number of $n$-words from $\{0, 1, 2, 3\}$ with an even number of zeros is $\displaystyle X_n=\frac{4^n+2^n}{2}$ and with an odd number of zeros is $\displaystyle Y_n=\frac{4^n-2^n}{2}$. But I have not been demonstrated the number $T_n$ of $n$-words have an even number of zeros and ones. Thanks for your help
 A: For a word $w$, let $w(k)$ be the number of times that $k$ appears in $w$, and $l(w)$ the length of $w$.
Let $A_n=\{w:l(w)=n,w(0)\text{ even and }w(1)\text{ even}\}$.
Let $B_n=\{w:l(w)=n,w(0)\text{ odd and }w(1)\text{ even}\}$.
Let $C_n=\{w:l(w)=n,w(0)\text{ even and }w(1)\text{ odd}\}$.
Let $D_n=\{w:l(w)=n,w(0)\text{ odd and }w(1)\text{ odd}\}$.
Take a word $w$ of length $n$ and let's try to generate a word of length $n+1$ by appening a digit to the end.
If $w\in A_n$ then the new digit can be $2$ or $3$.
If $w\in B_n$ the new digit must be $0$.
If $w\in C_n$ the new digit must be $1$.
If $w\in D_n$ no valid word can be generated this way.
Then:
$$|A_{n+1}|=2|A_n|+|B_n|+|C_n|$$
Similarly, we get:
$$|B_{n+1}|=|A_n|+2|B_n|+|D_n|$$
$$|C_{n+1}|=|A_n|+2|C_n|+|D_n|$$
$$|D_{n+1}|=|B_n|+|C_n|+2|D_n|$$
For word of length $1$, we have: $|A_1|=2$, $|B_1|=1$, $|C_1|=1$, $|D_1|=0$.
This set of equations allows you to find recursively any $|A_n|$.
In fact, given the matrix
$$M=\left(\begin{matrix}2&1&1&0\\1&2&0&1\\1&0&2&1\\0&1&1&2\end{matrix}\right)$$
the values for $|A_n|$, etc. are given by
$$M^n\left(\begin{matrix} 2\\ 1\\ 1\\ 0\end{matrix}\right)$$
