3
$\begingroup$

I'm just running through my midterm review.. I'm usually pretty bad at applying simple combinatorics to word problems.. So I just was wondering if anyone could confirm the following answers.

We're dealing with binary strings of length 10.

a) How many binary strings of length 10 have at least three 0's?

So, this is equal to the total number of binary strings of length 10 minus the number of binary strings of length 10 with zero, one, and two 0's.

zero 0's: There is only 1 string like this: 1111111111

one 0: There are ten places to place the one 0, and thus there are ten of such cases

two 0's: There are ten places to place the first 0 and nine places to place the second 0. However, there is an overlap so we divide by $2!$.

b)How many binary strings of length 10 have an even number of 1's?

So here I just applied the method I used for the number of strings with two 0's.

zero 1's: 1 string

two 1's: $\dfrac{10*9}{2!}$

four 1's: $\dfrac{10*9*8*7}{4!}$

six 1's: $\dfrac{10*9*8*7*6*5}{6!}$

eight 1's: $\dfrac{10*9*8*7*6*5*4*3}{8!}$

ten 1's: $\dfrac{10!}{10!}$

So if you sum all of that up, you get 512 strings which makes sense because $2^{10} = 1024$..

c) The number of binary strings of length 10 with alternating 0's and 1's

This one's really easy... There are only two options: $1010..$ and $0101..$

d) Four consecutive 0's

Here, there are $7$ places to put the block of zeros, then $2$ ways to fill in each remaining space, for a total of $7 * 2^6$ possible strings.

Any help / comments are greatly appreciated.

Cheers

  • 0
    For b) you might note that the number of even and odd strings is equal as you have a bijection between these two subsets, given by flipping e.g. the last bit.2012-10-21

1 Answers 1

3

d) needs a bit elaboration.

(i) If the question is about a run of exactly 4 $0$'s (though possibly a longer run elsewhere), we can count like this:

There are $2^5$ strings starting with $00001$. There are $2^5$ strings ending with $10000$. For $0\le k\le 4$ there are $2^4$ strings $\alpha100001\beta$, where $\alpha$ is $k$ digits and $\beta$ is $4-k$ digits long. Note that we need the "sentinel" $1$s to prevent the block from being longer than 4. That gives $2^5+2^5+5\cdot2^4=144$ strings. However, $0000100001$, $0000110000$, $1000010000$ are counted twice, thus the answer is: 141. Note that e.g. $0000100000$ is counted even though it has (also) a run of 5 0's.

(ii) If the question is about a run of at least 4 $0$'s, we can do this:

There are $2^6$ strings beginning with $0000$, i.e. with the block starting at the first digit. For $2\le k\le 6$, there are $2^5$ strings of the form $\alpha10000\beta$ with $\alpha$ of length $k-1$ and $\beta$ of length $6-k$, i.e. with the block starting at the $k$th digit. This give $2^6+5\cdot2^5=224$ strings. However, we counted solutions with two blocks twice, namely $0000100001$, $0000110000$, $1000010000$, $0000100000$, $0000010000$. (Fortunately, there is not much room for two blocks). Thus the answer is: 219.