Find a system of recurrence relations for computing the number of $n$-digit quaternary sequences with
(a) An even number of $0$s
(b) An even total number of $0$s and $1$s
(c) an even number of $0$s and an even number of $1$s
I am stuck on all parts of this problem. I have tried looking up solutions to this question and I am having trouble understand the rationale behind it.
For (a) I have attempted it:
When $n=2$, the number of sequences with an even number of $0$s is just one sequence: $00$
When $n=3$, the sequences can be: $001,002,003,010,020,030,100,200,300$: $9$ sequences
When $n=4$: the structures can be $00–, -00-,–00, 0-0-,0–0,$ or $-0-0$ and the sequence $0000$. For all the different structures there is a total of $3^2$ sequences so there are $6\times 3^2=54$ sequences. So when $n=4$ there are $54+1=55$ sequences.
I am not sure that this approach is right but it is my attempt and if it is correct then I am unsure where to go from here.
Best Answer
Let $a_n$ be the number of $n-$digit sequences with an even number of both $0$s and $1$s, let $c_n$ be the number of $n-$digit sequences with an odd number of both $0$s and $1$s, and let $b_n$ be the number of $n-$digit sequences with an even number of one and an odd number of the other. As stated in Find a system of recurrence relations foe computing the number of n-digit quaternary sequences with, we have $$ \begin{eqnarray*} a_n &=& 2a_{n-1} + b_{n-1} \tag{1}\\ b_n &=& 2a_{n-1} + 2b_{n-1} + 2c_{n-1}\tag{2} \\ c_n &=& b_{n-1} + 2c_{n-1}. \tag{3}\\ \end{eqnarray*} $$ From your comments, I gather that you understand the reason for $(1)$ (and, I suppose $(3)$, since it's essentially the same,)but are stuck on $(2).$ I'll only discuss $(2),$ therefore.
To get an "odd-even" sequence of $n$ digits, we can
This gives formula $(2)$, since there are no other ways to construct an odd-even sequence of length $n-1$.
Your last comment doesn't make sense as written. You say, "if there is an even number of $0$s and an odd number of $1$s in the first $n−1$ digits and the last digit is a $1$ then it becomes even−even and if the last digit is a $1$ then it becomes odd−odd." This gives two contradictory results if the last digit is a $1.$ I suppose there's a typo, but the statement has nothing to do with the case any way. Since we are looking for a formula for $b_n,$ we only care about how to make odd-even sequences.
You might find this table useful:$$ \begin{array}{|c|c|c|c|c|} \hline &OO&OE&EO&EE\\ \hline 0&EO&EE&OO&OE\\ \hline 1&OE&OO&EE&EO\\ \hline 2&OO&OE&EO&EE\\ \hline 3&OO&OE&EO&EE\\ \hline \end{array}$$
Here $OO$ stands for "odd-odd," $EO$ for "even-odd," and so on. Note that I've distinguished the case of an odd number of $0$ and an even number of $1$s from the case of an odd number of $1$ and an even number of $0$s. The top row shows the kind of string of $n-1$ digits we have, and the table entries show what kind of $n-$digit string we get if the digit in the left-hand column is added. Gathering together all these results, and then combining the odd-even and even-odd cases into one, will give all the recurrences.