0
$\begingroup$

Find a recurrence relation for the number of bit strings of length $n$ such that:

  1. number of all $0$s and $1$s is even.
  2. number of $0$s and number of $1$s is even.

Thank you.

  • 0
    OK 1) is trivial. The total of the number of 0s and 1s is n. For 1) the answer is $2^n$ when$n$is even and $0$ when $n$ is odd2012-12-21

1 Answers 1

1

(1) Let $a_n$ be the number of bit strings of length $n$ such that the total number of $0$’s and $1$’s is even. Clearly the total number of $0$’s and $1$’s is just the length of the bit string, and there are $2^n$ bit strings of length $n$, so

$a_n=\begin{cases} 2^n,&\text{if }n\text{ is even}\\ 0,&\text{if }n\text{ is odd}\;. \end{cases}$

This is a problem in which it’s actually easier to write down a closed form than a recurrence. If you must find a recurrence, you could note that $a_n=4a_{n-2}$ for all $n\ge 2$, with initial conditions $a_0=1$ and $a_1=0$.

(2) Let $b_n$ be the number of bit strings of length $n$ such that the number of $0$’s and the number of $1$’s in the string are both even. Clearly $b_n=0$ when $n$ is odd. Suppose that $n$ is even and positive. If $\sigma$ is an $n$-bit string, imagine removing the last two bits. If they are $01$ or $10$, the remaining $(n-2)$-bit string will have an odd number of $1$’s and an odd number of $0$’s. If they are $00$ or $11$, the the remaining $(n-2)$-bit string will have an even number of $1$’s and an odd number of $0$’s. In other words, each ‘good’ $n$-bit string is obtained either by appending $00$ or $11$ to a ‘good’ $(n-2)$-bit string or by appending $01$ or $10$ to a ‘bad’ $(n-2)$-bit string. From this you can calculate $b_n$ quite easily.

  • 0
    @Maya: You have too many: there are $2^n$ bit strings of length $n$ altogether, and they aren’t all good, so $b_n$ must be less than $2^n$. Here’s a simpler approach: **every** $(n-2)$-bit string produces exactly $2$ good $n$-bit strings. There are $2^{n-2}$ bit strings of length $n-2$, so there must be $2\cdot2^{n-2}=2^{n-1}$ good bit strings of length $n$: $b_n=2^{n-1}$ when $n$ is even, and $0$ when $n$ is odd.2012-12-21