Combinatorics problem with bit-strings

Question

When only three types of bit strings 0, 10,11 are available, how many valid $7$-bit strings can be represented? For example, the bit string 0101110, which is composed of 0, 10, 11, 10, is a valid bit string, but 1100101 is invalid.

Answer 1

Define $f(n)$ as the number of valid $n$-bit strings and define the empty string as valid. So $f(0)=f(1)=1$. We can create a valid string of length $n$ by taking a string of length $n-1$ and appending "$0$" or by taking a string of length $n-2$ and appending either "$10$" or "$11$". So, we have $f(n)=f(n-1)+2f(n-2)$. From here, we get

$$f(2)=f(1)+2f(0)=1+2=3$$ $$f(3)=f(2)+2f(1)=3+2=5$$ $$f(4)=f(3)+2f(2)=5+6=11$$ $$f(5)=f(4)+2f(3)=11+10=21$$ $$f(6)=f(5)+2f(4)=21+22=43$$ $$f(7)=f(6)+2f(5)=43+42=85$$

Answer 2

The available strings form whats called a "prefix code", which means that no string is the prefix of another string. This allows us to create a simple algorithm that determines if a bit string is valid or not. Think of the bit string as a stream. Read in a character. If it is 0, discard it and move on to the next character. If it is a 1, then discard it and the next character.

In the first case, we are removing an instance of the 0 string. In the second, we are removing an instance of either 10 or 11.

This process only fails if you read in a 1 but there is no character following it.

Therefore, the only invalid strings are strings which end in a single 1. Can you finish the problem from here?

Edit: @YawarRaza7349 pointed out a potential misinterpretation; I'll complete this solution to avoid that.

• Since all invalid strings end in 1, we know that all strings ending in 0 are valid. This already gives us $2^6=64$ valid strings.
• Next, the only way for a valid string to end in a 1 is for the last two characters to be 11. If we remove these characters, we are left with $5$ characters that also form a valid string.
• Thus we can apply the same argument again. If the last of these $5$ characters is 0, the string is valid. This gives $2^4=16$ valid strings.
• Iterating again, we have $3$ characters which form a valid string and there are $2^2=4$ possibilities.
• Finally, we have just a single character string that is valid, there is only $2^0=1$ option.
• Summing, we have $2^6+2^4+2^2=64+16+4+1=85$.

Answer 3

The numbers 11 and 10 have 2 digits(2 bits) and 0 has a single digit(1 bit). The 7 bits can be formed in 4 cases: 1) three 2 bits and one 1 bit 2) two 2 bits and three 1 bits 3) one 2 bit and five 1 bits 4) zero 2 bits and seven 1 bits.

Case 1: _ _ _ 0 the first three blanks can be filled in 8 ways(2 ways for 1st blank{because it can be filled by 10 or 11}, 2 ways in 2nd and the same goes for the 3rd).

so by product rule 2*2*2=8 ways

Case 2: _ _ 0 0 0 the first two blanks can be filled in 4 ways( 2 ways for 1st and in two for 2nd).

so by product rule we have 2*2 = 4.

Case 3: _ 0 0 0 0 0 the first blank can be filled in 2 ways(with 10 or 11).

so this equals 2.

Case 4: 0 0 0 0 0 0 0 this is applicable in only one way.

(i didn't have the need to choose the one bit because it is 0 for sure)

now to obtain the final answer add all the cases.

which equals 8 + 4 + 2 + 1 = 15.

therefore there 15 strings.

I am happy to receive any corrections if this is wrong :)