Binary Concatenations

Probability Level 5

How many strings of length 8 are there that can be formed by concatenating strings of the form "0", "10" and "11"?

Note: Each of the strings "0", "10" and "11" could be used several times. For example, we can concatenate "0", "10", "10", "0", "10", "10", "0", "0", "10" to get "01010010100010", a string of length 14.

Details and assumptions

String concatenation refers to joining 2 (or more) strings end-to-end, and treated as 1 string. For example, if we concatenate the string "Brilli" of length 6 and string "ant" of length 3, we get the string "Brilliant" of length 9.

The answer is 171.

2 solutions

Daniel Chiu
Dec 27, 2013

We use recursion on the length of the string. If a string has length $n$ , then a string of length $n+2$ can be formed by adding "10" or "11", and a string of length $n+1$ can be formed by adding "0". Hence, we have the recursion, where $f(n)$ denotes the number of strings of length $n$ , $f(n)=f(n-1)+2f(n-2)$ Computing, we find the values $f(1)=1,f(2)=3,f(3)=5,f(4)=11,f(5)=21,f(6)=43,f(7)=85,f(8)=\boxed{171}$

This problem really does have a recursive feel built into it. However due to my lack of experience with recursion(I better get it down by reading your article later), it wasn't the first thing that came to my mind. Instead, I thought about what can(cannot) be constructed by these given strings.

We can build as many 0s in a row as we want, but an odd number of 1s in a row must have a 0 after the last 1. This tells us that we can't have an odd number of consecutive 1s as the rear of the string. In other words, our strings can't end in: 01,0111,011111,01111111. Each of which can be part of $2^6,2^4,2^2,2^0$ strings. Hence our answer is total possible strings-unwanted strings: $2^8-2^6-2^4-2^2-2^0=171$ .

Xuming Liang - 7 years, 5 months ago

dude.........this solution proves ur genous........

Suyash Gupta - 7 years, 5 months ago

Interesting solution! Out of curiosity, how long did it take you to come up with this?

Daniel Chiu - 7 years, 5 months ago

It's worth noting in Daniel's solution that strings formed by adding "10" to a string of length $n$ and strings formed by adding "0" to a string of length $n+1$ are mutually exclusive.

To prove this, we can use the fact that any string must end in an even number of consecutive 1's (Xuming shows this in his solution.) Thus, by adding "10" to a string of length $n$ , we form a new string with an odd number of consecutive 1's before the final "0." However, by adding "0" to a string of length $n+1$ , we form a string with an even number of consecutive 1's before the final "0." Thus, the two sets of strings share no common elements.

This result seems necessary for the recursion to work. I didn't realize this when I attempted recursion, so I eventually found a solutions similar to Xuming's.

Omid Rooholfada - 7 years, 5 months ago

Yeah, I did think about whether the strings would repeat. I decided that it wouldn't be too difficult to prove (consider parity of 1's in a row and 0's are decided), and since the question was slightly ambiguous about whether that was important, I left it out.

Daniel Chiu - 7 years, 5 months ago

If we solve this recurrence relation, with f(0) = f(1) = 1, we obtain $f(n) \; = \; \tfrac13\big[2^{n+1} + (-1)^n\big]$ so that $f(8) = \tfrac13(2^9 + 1) = 171$ .

Mark Hennings - 7 years, 1 month ago

Aditya Joshi
Dec 28, 2013

There are precisely 5 ways to make a string of '1', '10' and '11'

Use

0 '0's and a combination of 4 '11' and/or '10's
2 '0's and a combination of 3 '11' and/or '10's
4 '0's and a combination of 2 '11' and/or '10's
6 '0's and a combination of 1 '11' and/or '10's
8 '0's and a combination of 0 '11' and/or '10's

For the first option, we have to arrange '10' and '11' and 0 '0's. We have 4 place holders for doing so. We can do this in $2^{4}$ ways.

For the second option, we have to arrange 3 '10' and '11's and 2 '0's. There are 3 placeholders (for '10' and '11') and for every placeholder we have 2 choices. We can do this in $2^{3} \times {5 \choose 3}$ ways.

For the third option, we have to arrange 2 '10' and '11's and 4 '0's. There are 2 placeholders (for '10' and '11') and for every placeholder we have 2 choices. This can be done in $2^{2} \times {6 \choose 2}$ ways.

For the fourth option, we have to arrange 1 '10' and '11's and 6 '0's. There is 1 placeholder (for '10' and '11'). We can arrange this in $2 \times {7 \choose 1}$ ways.

Finally, we can arrange 8 '0's in exactly 1 way.

So that is

$16 + 80 + 60 + 14 + 1 = \boxed{171}$ ways

Binary Concatenations

The answer is 171.

2 solutions

0 pending reports