0

You are given all n-digit strings in which each digit is 0, 1, or 2. Using the product rule and/or the sum rule, count the number of these strings that have an odd number of 0’s when n (the number of digits in the string) is equal to

(a) 1

I got $1$ string, which is $0$

(b) 2

$2\times1 = 2$ and $1 \times 2 = 2.$

Then $2+2=4$ strings.

(c) 3

We can have 1 or 3 $0$'s.

For 1: $1\times2\times2=4$ and $2\times1\times2=4$ and $2\times2\times1=4$

For 3: $1\times1\times1=1$

Then, $4+4+4+1=13$ strings.

(d) 4.

We can have 1 or 3 $0$'s.

For 1: $1\times2\times2\times2=8$ and $2\times1\times2\times2=8$ and$2\times2\times1\times2=8$ and $2\times2\times2\times1=8$

For 3: $1\times1\times1\times2=2$ and $1\times1\times2\times1=2$ and $1\times2\times1\times1=2$ and $2\times1\times1\times1=2$

Then, $8+8+8+8+2+2+2+2=40$ strings.

Using recurrence relations, count the number of these strings that have an odd number of 0’s in all n-digit strings. Once you get the (closed-form) formula, verify that your answers to (a) through (d) are correct.

Ludwigthestud
  • 195

1 Answers1

1

Hint: Let $E(n)$ be the number of strings with an even number of zeros and $O(n)$ be the number with an odd number of zeros. Can you write an equation for $E(n)$ in terms of $E(n-1), O(n-1)$ and similarly for $O(n)?$ If you have string of length $n-1$ with an even number of zeros and extend it by one digit...

Added: a string of $n$ digits with an odd number of $0$'s can come from a string of length $n-1$ with an odd number of $0$'s that we add a $1$ or a $2$ to, or from a string of length $n-1$ with an even number of $0$'s that we add a $0$ to. The recurrence is then $O(n)=2O(n-1)+E(n-1)$. Similarly we have $E(n)=2E(n-1)+O(n-1)$. The base condition is $O(0)=0,E(0)=1$ because the empty string has an even number of $0$'s.

We know $E(n)+O(n)=3^n$ because every string of length $n$ has either an even or odd number of $0$'s. We then have $$O(n)=2O(n-1)+3^{n-1}-O(n-1)\\O(n)=3^{n-1}+O(n-1)$$ and we can sum the geometric series to get $$O(n)=\frac 12(3^n-1)\\E(n)=\frac 12(3^n+1)$$

Ross Millikan
  • 374,822
  • I've gotten a sequence ${1,4,13,40,...}$. So, $O(0) = 1$ is the initial condition, and $O(n) = 3(O(n-1))+1$ is the recurrent condition. Am I getting there? – Ludwigthestud Oct 09 '18 at 20:13
  • 1
    No, $O(0)=0$ because the empty string does not have an odd number of zeros. $E(0)=1$. Then an odd string of length $n$ is either an odd string of length $n-1$ with a $1$ or $2$ added or an even string of length $n-1$ with a $0$ added. I agree with your $1,4,13,40\ldots$. Your recurrence produces the right answers but I don't see how it is justified. – Ross Millikan Oct 09 '18 at 20:19
  • Hmm. Then the sequence is actually $0,1,4,13,40,....$ , right? – Ludwigthestud Oct 09 '18 at 20:31
  • 1
    Yes, that is correct. It is $\frac 12(3^n-1)$ – Ross Millikan Oct 09 '18 at 20:33
  • Ok, then $O(0) = 0$ is the initial condition. $O(n)=3(O(n-1))+1$ , $n \geq 1$ is the recurrent. I feel like I'm still way off. – Ludwigthestud Oct 09 '18 at 20:42
  • Just saw that^. Disregard. – Ludwigthestud Oct 09 '18 at 20:43