Combinatorics problem with bit-strings [closed]

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.

closed as off-topic by user21820, Did, Namaste, Holo, ccornSep 2 '18 at 15:23

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – user21820, Did, Namaste, Holo, ccorn
If this question can be reworded to fit the rules in the help center, please edit the question.

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$$

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$.
• Your last paragraph could be read as implying that the answer is the number of 7-bit strings that end in 1, which isn't correct. Valid strings where 11 was consumed last also end in 1. – YawarRaza7349 Sep 2 '18 at 9:12
• Sorry, I meant "the number of 7-bit strings that don't end in 1". – YawarRaza7349 Sep 2 '18 at 10:40
• @YawarRaza7349 thanks, I updated my answer. – rikhavshah Sep 2 '18 at 15:29
• Interesting alternative to the one in Mike's answer. Another fix though: you need to take one more step and add $2^0$ (for the string 0111111). (I'm also not sure what you mean by "excluding the empty string"; it wasn't explicitly excluded, it wasn't counted like for the same reason all other strings that aren't 7 bits long weren't counted.) – YawarRaza7349 Sep 2 '18 at 15:50
• I think this formulation uses a recurrence relation $g(n)$ defining the number of invalid n-bit strings, i.e. the complement of Mike's answer. – smci Sep 2 '18 at 21:44

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)

• The valid example the OP mentioned in the beginning, 0 10 11 10, starts with a 0, and thus is not counted in any of your cases. – YawarRaza7349 Sep 2 '18 at 14:13