Find a recurrence relation for the number of bit strings of length $n$ such that:
- number of all $0$s and $1$s is even.
- number of $0$s and number of $1$s is even.
Thank you.
Asked
Active
Viewed 1,726 times
0
Maya
- 55
-
What is the difference between 1) and 2) – Amr Dec 21 '12 at 12:20
-
In 1) number of "all" 0s And 1s is even. – Maya Dec 21 '12 at 12:34
-
Do you mean that the total number of 0s and 1s is even – Amr Dec 21 '12 at 12:35
-
yes, for example: for 1) $001011$ is true and $0010110$ is false. – Maya Dec 21 '12 at 12:41
-
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 odd – Amr Dec 21 '12 at 12:43
1 Answers
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.
Brian M. Scott
- 616,228
-
we have $2 a_{n-2}$ good bit string and $(2^{n-1}-a_{n-2})$ bad string of length $n-2$ that add $00$ or $11$ by $2$ ways,and we have $2(2^{n-1}-a_{n-2})$ good string , $b_n=2(2^{n-1}-a_{n-2})+2 a_{n-2}=2^n$ is it true? – Maya Dec 21 '12 at 13:39
-
@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. – Brian M. Scott Dec 21 '12 at 13:43