Question

Counting bit strings. How many 10-bit strings are there subject to each of the following restrictions? (a) No restrictions. The string starts with 001. The string starts with 001 or 10. The first two bits are the same as the last two bits. The string has exactly six o's. The string has exactly six O's and the first bit is 1. There is exactly one 1 in the first half and exactly three 1's in the second half.

Answer 1

Answer:

a) With no restrictions, there are 1024 possibilies

b) There are 128 possibilities for which the tring starts with 001

c) There are 256+128 = 384 strings starting with 001 or 10.

d) There are 128  possiblities of strings where the first two bits are the same as the last two bits

e)There are 210 possibilities in which the string has exactly six 0's.

f) 84 possibilities in which the string has exactly six O's and the first bit is 1

g) 50 strings in which there is exactly one 1 in the first half and exactly three 1's in the second half

Step-by-step explanation:

Our string is like this:

B1-B2-B3-B4-B5-B6-B7-B8-B9-B10

B1 is the bit in position 1, B2 position 2,...

A bit can have two values: 0 or 1

So

No restrictions:

It can be:

2-2-2-2-2-2-2-2-2-2

There are $2^{10} = 1024$ possibilities

The string starts with 001

There is only one possibility for each of the first three bits(0,0 and 1) So:

1-1-1-2-2-2-2-2-2-2

There are $2^{7} = 128$ possibilities

The string starts with 001 or 10

There are 128 possibilities for which the tring starts with 001, as we found above.

With 10, there is only one possibility for each of the first two bits, so:

1-1-2-2-2-2-2-2-2-2

There are $2^{8} = 256$ possibilities

There are 256+128 = 384 strings starting with 001 or 10.

The first two bits are the same as the last two bits

The is only one possibility for the first two and for the last two bits.

1-1-2-2-2-2-2-2-1-1

The first two and last two bits can be 0-0-...-0-0, 0-1-...-0-1, 1-0-...-1-0 or 1-1-...-1-1, so there are $4*2^{6} = 256$ possiblities of strings where the first two bits are the same as the last two bits.

The string has exactly six o's:

There is only one bit possible for each position of the string. However, these bits can be permutated, which means we have a permutation of 10 bits repeatad 6(zeros) and 4(ones) times, so there are

$P^{10}_{6,4} = \frac{10!}{6!4!} = 210$

210 possibilities in which the string has exactly six 0's.

The string has exactly six O's and the first bit is 1:

The first bit is one. For each of the remaining nine bits, there is one possiblity for each.  However, these bits can be permutated, which means we have a permutation of 9 bits repeatad 6(zeros) and 3(ones) times, so there are

$P^{9}_{6,3} = \frac{9!}{6!3!} = 84$

84 possibilities in which the string has exactly six O's and the first bit is 1

There is exactly one 1 in the first half and exactly three 1's in the second half

We compute the number of strings possible in each half, and multiply them:

For the first half, each of the five bits has only one possibile value, but they can be permutated. We have a permutation of 5 bits, with repetitions of 4(zeros) and 1(ones) bits.

So, for the first half there are:

$P^{5}_{4,1} = \frac{5!}{4!1!} = 5$

5 possibilies where there is exactly one 1 in the first half.

For the second half, each of the five bits has only one possibile value, but they can be permutated.  We have a permutation of 5 bits, with repetitions of 3(ones) and 2(zeros) bits.

$P^{5}_{3,2} = \frac{5!}{3!2!} = 10$

10 possibilies where there is exactly three 1's in the second half.

It means that for each first half of the string possibility, there are 10 possible second half possibilities. So there are 5+10 = 50 strings in which there is exactly one 1 in the first half and exactly three 1's in the second half.