Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Binary string length 10 with two 0's: there are (10)(9)/2 or 45 such strings. So 0,1,2 zeros is 1+10+45=56 strings. AAlso on your last one I think you counted some strings twice, say if one had a string of 8 consec 0 then two 1 would enter into several of your cases at once. –  coffeemath Oct 21 '12 at 19:58
    
In (a), you surely mean "so we divide by 2!", not "so we divide by 10!(sic)". Especially since you got it right in (b). Otherwise, looks fine AFAICS. Though (d) is a ambigous - the way the question is phrased it could also mean "exactly four consecutive 0s" instead of "at least four consecutive 0s". –  fgp Oct 21 '12 at 20:06
2  
You've counted some strings more than once in (d). For example, how many times does your approach count the string 0000010000? –  Michael Joyce Oct 21 '12 at 20:08
    
@fgp Yes I did mean divide by 2!, thank you. Working on (d) now, I'll update soon. THanks for the help guys! –  connorbode Oct 21 '12 at 20:10
    
Note that b) can be done using the fact that the alternating sum of binomial coefficients vanishes, so the sum of the even ones is equal to the sum of the odd ones, so both sums must be half the total, which as you note is $2^{10}=1024$. –  joriki Oct 21 '12 at 20:52
show 1 more comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.