Q:

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

Accepted Solution

A:
Answer:a) 1024b) 128c) 384d) 256e) 210f) 84g) 50Step-by-step explanation:Each bit has 2 possible values, either it is 0 or 1.How many 10-bit strings are there subject to each of the following restrictions? (a) No restrictions.If there are no restrictions, any of the 10 bits can assume any of these two values. So there are [tex]2^{10} = 1024[/tex] possibilites.(b) The string starts with 001. For each of the first three bits, there is only one possible value(0,0, then 1). For the final 7, there are two possible outcomes for each bit.So there are [tex]2^{7} = 128[/tex] possibilites.(c) The string starts with 001 or 10With 001, we have 128 possiblities, from b).WIth 10, there is only one possibility for the first two values and two each of the final eight. So starting with 10, there are [tex]2^{8} = 256[/tex] possibilities.There are 128+256 = 384 strings starting with 001 or 10.(d) The first two bits are the same as the last two bits.In the first and last bits, we can have 0-0 and 0-0, 0-1 and 0-1, 1-0 and 1-0, 1-1 and 1-1, so 4 possibilities.Now, for the middle 6, any of them can take two values.So there are [tex]4*2^{6} = 256[/tex] possibilities.e) 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[tex]P^{10}_{6,4} = \frac{10!}{6!4!} = 210[/tex]210 possibilities in which the string has exactly six 0's.f) 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[tex]P^{9}_{6,3} = \frac{9!}{6!3!} = 84[/tex]84 possibilities in which the string has exactly six O's and the first bit is 1g) There is exactly one 1 in the first half and exactly three 1's in the second halfWe 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:[tex]P^{5}_{4,1} = \frac{5!}{4!1!} = 5[/tex]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.[tex]P^{5}_{3,2} = \frac{5!}{3!2!} = 10[/tex]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.