What is the number of strings at size $n$ that is constructed from ${a,b,c,d}$ and there is an even num of $a$

Question

What is the number of strings at size $n$ that is constructed from ${a,b,c,d}$ and there is an even num of $a$?

I have tried to answer it as recursion formula in the following logic:

In order to build $ A(n) $, I will split into several cases:

1. if the string starts with $a$, then I will need another $a$ to make an even number of $a's$. so we get $aa[A(n-2)]$ meaning 2 $a's$ at the start + a valid string at the size of $n-2$.
2. if it starts with $b,c,d$ we get $b[A(n-1)]$ + $c[A(n-1)]$ +$d[A(n-1)]$, meaning a one of the letters + a valid string at the size of $n-1$.

So we will get a recursion formula that looks like that:

$A(n) = A(n-2) + 3A(n-1)$

I'm not 100% on my answer, am I right to approach it in that direction?

Answer 1

Consider two cases.

Case 1. The string is all $c$'s and $d$'s. There are $2^n$ such strings, and each of them has an even number of $a$'s, namely zero.

Case 2. The string is not all $c$'s and $d$'s. There are $4^n-2^n$ such strings, and exactly half of them, that is $\frac{4^n-2^n}2$, have an even number of $a$'s. (Why? Find the leftmost letter which is not $c$ or $d$, and flip it from $a$ to $b$ or from $b$ to $a$, thus changing the parity of the number of $a$'s.)

So the answer is $2^n+\frac{4^n-2^n}2=\boxed{\frac{4^n+2^n}2}=\boxed{2^{n-1}(2^n+1)}=$ A007582.

More generally, for strings over a $k$-letter alphabet, the number of strings of length $n$ in which a specified letter occurs an even number of times is $$\frac{k^n+(k-2)^n}2.$$

P.S. More detailed explanation of Case 2, as requested in a comment.

Let $S$ be the set of all strings (of length $n$) which are not all $c$'s and $d$'s; so $|S|=4^n-2^n$. Partition $S$ into two subsets $D$ and $E$, where $D$ is the set of all strings in $S$ with an odd number of $a$'s, and $E$ is the set of all strings in $S$ with an even number of $a$'s.

Define a map $f:S\to S$ as follows. Given a string $x\in S$, find the first letter in $x$ (reading from left to right) which is not a $c$ or a $d$; if it's an $a$ change it to $b$; if it's a $b$ change it to $a$. For example, $f(cadb)=cbdb$, $f(cbdb)=cadb$. Note that $f$ is an involution ($f(f(x))=x$), and $f$ swaps $D$ and $E$, i.e., $f(D)=E$ and $f(E)=D$. It follows that $|D|=|E|$ and so $|E|=\frac{|S|}2=\frac{4^n-2^n}2$, and the total number of strings with an even number of $a$'s is $2^n+|E|=\frac{4^n+2^n}2$.

Let $R$ be the set of all strings which are all $b$'s, $c$'s, and $d$'s, and contain at least one $b$; so $|R|=3^n-2^n$ and $R\subseteq E\subseteq S$. (The set $R$ plays no special role in my argument, but a commenter was asking about it.) The involution $f$ pairs elements of $R$ with strings in $D$ which contain exactly one $a$ and the $a$ precedes all the $b$'s; for example, if $n=4$, then $cbdb$ is paired with $cadb$.

Answer 2

That's close. Consider an $n$-letter word with an even number of A's. There are two cases:

• If the last character is not an A, then removing it gives an $n-1$ letter word with an even number of A's. Since there are 3 possibilities for the last letter (B, C, D), this accounts for $3A(n-1)$ cases.

• If the last character is an A, then removing it gives an $n-1$ letter word with an odd number of A's. There are clearly $4^{n-1}-A(n-1)$ of those.

That gives us $A(n)=3A(n-1)+4^{n-1}-A(n-1)=4^{n-1}+2A(n-1)$, and we have to toss in a base case of $A(1)=3$.

Answer 3

A systematic approach is to form the finite state automaton of the strings you accept:

Then, for all possible $n$ we have the number of strings of that length that end up each state described by repeating the transition matrix $n$ times for our finite state automaton $F$:

$$F(n) = \begin{bmatrix} 3 &1\\ 1 &3\\ \end{bmatrix}^n\begin{bmatrix} 1\\0 \end{bmatrix}$$

The above matrix can be diagonalized:

$$F(n) = \frac{1}{2}\begin{bmatrix} -1 &1\\ 1 &1\\ \end{bmatrix}\begin{bmatrix} 2 &0\\ 0 &4\\ \end{bmatrix}^n\begin{bmatrix} -1 &1\\ 1 &1\\ \end{bmatrix}\begin{bmatrix} 1\\0 \end{bmatrix}$$

And simplified:

$$F(n) = \frac{1}{2}\begin{bmatrix} -1 &1\\ 1 &1\\ \end{bmatrix}\begin{bmatrix} 2^n &0\\ 0 &4^n\\ \end{bmatrix}\begin{bmatrix} -1\\1 \end{bmatrix}$$

$$F(n) = \frac{1}{2}\begin{bmatrix} -1 &1\\ 1 &1\\ \end{bmatrix}\begin{bmatrix} -2^n\\ 4^n\end{bmatrix}$$ $$F(n) = \frac{1}{2}\begin{bmatrix} 4^n + 2^n\\ 4^n - 2^n\end{bmatrix}$$

Since we are interested in the number of even strings, we have:

$$A(n) = F(n) \begin{bmatrix}1&0\end{bmatrix} = \frac{1}{2}(4^n + 2^n)$$