The letter A appears an even number of times. How many different sequences could Dr. Lizardo have written down?

Question

Dr. Lizardo writes down a sequence of $n$ letters, where each letter is A, B, or C, and the letter A appears an even number of times. How many different sequences could Dr. Lizardo have written down?

---

What I have tried so far

The last letter is predefined in terms of "A or not" based on the first $n-1$ letters. If there are an odd number of As so far, the last one has to be A, otherwise, B or C. Therefore, there are $3^{n-1}$ ways to write the first $n-1$ letters. However, the last letter can either have 1 choice or 2 choices.

I am thinking maybe we need to do $S_n = 3^{n-1} + S_{n-1}$. However, I need a closed form, not a recurrance. How can I do this?

Thank you!

---

Note: $S_n = 3^{n-1} + S_{n-1}$ seems to be working for the first few values of $n$ (I tested through $n=4$), so finding a closed form of that recurrance would work as well.

Answer 1

Consider two cases.

Case 1. The sequence is all C's. There is just one such sequence, and it has an even number of A's, namely zero.

Case 2. The sequence is not all C's. There are $3^n-1$ such sequences, and exactly half of them, or $\frac{3^n-1}2$, have an even number of A's. To see this, look at the leftmost letter in the sequence that's not a C; toggling it between A and B, we see that there's a one-to-one correspondence between sequences with an even and an odd number of A's.

Combining the results from Case 1 and Case 2, we get a grand total of $$1+\frac{3^n-1}2=\frac{3^n+1}2.$$

More generally, over an alphabet of $k$ letters, the number of sequences of length $n$ in which a certain letter appears an even number of times is $$(k-2)^n+\frac{k^n-(k-2)^n}2=\frac{k^n+(k-2)^n}2;$$ see my answer to this question.

Answer 2

Setting $S_0 = 1$ (the empty sequence definitely has an even number of 'A's) and then defining $S_n = 3^{n-1} + S_{n-1}$ for $n \geq 1$ gives $$S_n = S_0 + \sum_{k=0}^{n=1}3^k = 1 + \frac{1-3^n}{1-3} = \frac{3^n+1}{2}$$

where we have used the formula for the finite geometric series $$\sum_{k=0}^{n-1}ar^k = \frac{a(1-r^n)}{1-r}$$

---

Another way to see this is to use generating functions: $$P(x,y,z) = (x+y+z)^n = \sum_{\substack{i,j,k \geq 0 \\ i+j+k=n}} S(i,j,k)x^iy^jz^k$$ is the generating function for the number of sequences $S(i,j,k)$ with $i$ 'A's, $j$ 'B's, and $k$ 'C's. We want to find $$\sum_{\substack{i,j,k \geq 0 \\ i+j+k=n \\ 2|i}} S(i,j,k)$$

To impose the assumption that $i$ is even, we take the even part with respect to $x$: $$\frac{P(x,y,z) + P(-x,y,z)}{2} = \sum_{\substack{i,j,k \geq 0 \\ i+j+k=n \\ 2|i}} S(i,j,k)x^iy^jz^k$$

and then we just evaluate at $x=y=z=1$: $$\frac{(1+1+1)^n + (-1+1+1)^n}{2} = \sum_{\substack{i,j,k \geq 0 \\ i+j+k=n \\ 2|i}} S(i,j,k)$$

which we note simplifies once again to $\frac{3^n+1}{2}$

Answer 3

Good analysis, but a closed form requires that you get down in the mud.
Note : possible exception is if someone can provide a more elegant computation than my kludgy approach.

Let $c = \lfloor \frac{n}{2}\rfloor.$

That is $c$ is the largest integer such that $2c \leq n$.

Then, you want

$$\sum_{k=0}^c f(k)$$,

where $f(k)$ is the exact # of ways of having $2k$ A's in the sequence.

There are $\binom{n}{2k}$ ways of distributing the $2k$ A's.

There are $2^{(n-2k)}$ ways of choosing B or C for the $(n - 2k)$ other slots.

Therefore,

$$f(k) = \binom{n}{2k} \times 2^{(n-2k)}.$$

It is unclear to me whether the summation can be expressed in a simpler fashion.

Answer 4

This is a bit more of a linear algebra proof which is probably not what you are seeking but I'd still like to share it anyways. Define two sequences $a_n$ being the number of length-$n$ sequences with even number of As and $b_n$ being the number of length-$n$ sequences with odd number of As. Clearly $a_0 = 1$ and $b_0 = 0$

Notice that the if you have an length-$(n-1)$ sequences with even number of As: there are two ways to add one character (either B or C) so that the new length-$n$ sequence has even As and there is one way to add one character (A) so that the new length-$n$ sequence has odd As.

Similarly if you have an length-$(n-1)$ sequences with odd number of As: there is one way to add one character (A) so that the new length-$n$ sequence has even As and there are two ways to add one character (B or C) so that the new length-$n$ sequence has odd As.

From here we can define a recurrence relation in terms of matrices $$ \left( \begin{matrix} a_{n} \\ b_{n} \end{matrix} \right) = \left( \begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix} \right) \left( \begin{matrix} a_{n-1} \\ b_{n-1} \end{matrix} \right) = \left( \begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix} \right)^n \left( \begin{matrix} a_{0} \\ b_{0} \end{matrix} \right)$$

If we diagonalize this matrix we get $$ \left( \begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix} \right) = \left( \begin{matrix} -1 & 1 \\ 1 & 1 \end{matrix} \right) \left( \begin{matrix} 1 & 0 \\ 0 & 3 \end{matrix} \right) \frac{1}{2} \left( \begin{matrix} -1 & 1 \\ 1 & 1 \end{matrix} \right)$$

$$ \left( \begin{matrix} a_{n} \\ b_{n} \end{matrix} \right) = \left( \begin{matrix} -1 & 1 \\ 1 & 1 \end{matrix} \right) \left( \begin{matrix} 1 & 0 \\ 0 & 3^n \end{matrix} \right) \frac{1}{2} \left( \begin{matrix} -1 & 1 \\ 1 & 1 \end{matrix} \right) \left( \begin{matrix} 1 \\ 0 \end{matrix} \right) = \frac{1}{2} \left( \begin{matrix} 3^n+1 \\ 3^n-1 \end{matrix} \right)$$

thus $a_n = \frac{3^n+1}{2}$

Answer 5

Here we show the equality of two already given answers. The number $S_n$ is given by

\begin{align*} \color{blue}{S_n=\frac{1}{2}\left(3^n+1\right)=\sum_{k=0}^n\binom{n}{2k}2^{n-2k}\qquad\qquad n\geq 0}\tag{1} \end{align*}

The following is valid \begin{align*} \sum_{k=0}^{n}\binom{n}{2k}x^{2k}+\sum_{k=0}^n\binom{n}{2k+1}x^{2k+1}&=(1+x)^n\\ \sum_{k=0}^{n}\binom{n}{2k}x^{2k}-\sum_{k=0}^n\binom{n}{2k+1}x^{2k+1}&=(1-x)^n\\ \sum_{k=0}^n\binom{n}{2k}x^{2k}&=\frac{1}{2}\left((1+x)^n+(1-x)^n\right)\tag{2} \end{align*}

We obtain from (2) \begin{align*} \color{blue}{\sum_{k=0}^n\binom{n}{2k}2^{n-2k}} &=2^n\sum_{k=0}^n\binom{n}{2k}\left(\frac{1}{2}\right)^{2k}\\ &=2^n\,\frac{1}{2}\left(\left(1+\frac{1}{2}\right)^n+\left(1-\frac{1}{2}\right)^n\right)\\ &=2^n\,\frac{1}{2}\left(\left(\frac{3}{2}\right)^n+\left(\frac{1}{2}\right)^n\right)\\ &\,\,\color{blue}{=\frac{1}{2}\left(3^n+1\right)} \end{align*} and the claim (1) follows.