# Homework Help: Counting methods help please

1. Apr 18, 2004

### ptex

The question is how many 8-bit strings have either the second or the fourth bit 1 (or both)?
I know the soulution is 3*2^6 but why??

Also this question how many 8 bit strings begin and end with 1? is it 8C2?

Last edited: Apr 18, 2004
2. Apr 18, 2004

### pig

1. If the second bit is 1, we 7 variable bits so that is 2^7 different combinations. In this, the combinations where the fourth bit is also 1 are included, so we have to add the number of combinations where the second bit is 0 and the fourth bit is 1 and that is an additional 2^6. 2^7 + 2^6 = 192 (This is your 3*2^6).

2. I don't know what 8C2 means but if the 8 bit string begins and ends with a 1 then we have 6 variable bits, each with 2 possible values so it's 2^6 = 64.

Don't be discouraged by problems like this, you don't need any "formulas" for stuff like this, just think this way (for example, in the second question):

We have to count all possible bit strings of the form 1xxxxxx1. There is 1 possibility for the first bit, 1, for that there is 2 possibilities for the second bit, 0 and 1, for each of those there are 2 possibilities for the third bit, for each of those ... there are 2 possibilities for the seventh bit, for each of those there is 1 possibility for the eighth bit. That is 1*2*2*2*2*2*2*1 = 2^6 = 64

If something is unclear, ask. :)

Last edited: Apr 18, 2004
3. Apr 18, 2004

### ptex

Why 2? Because we are talking about 2 bits?

4. Apr 18, 2004

### pig

No. Because a bit has 2 possible values - 0 and 1.

For example, let's say we want to count all strings of 4 letters which begin with letter 'a' or 'f' and end with anything except 'c'.

We have 2 possibilities for the first letter (a and f). For each of those 2, we have 26 possibilities for the second letter (any letter), for each of those we have 26 possibilities for the third letter (any letter), for each of those we have 25 possibilities for the fourth letter (anything but c).

So that's 2*26*26*25. :)

5. Apr 18, 2004

### ptex

Thank you I will ponder this for a few and try a few more problems. Again thank you.