Constructing a binary string of length $12$

Question

You construct a binary sequence of length $12$ consisting of seven zeros and five ones.

(a) How many strings are there?

(b) How many of them have no two consecutive zeros?

(c) How many have at least three ones among the first four entries?

(d) How many do not contain the substring $0000$?

(e) How many strings are there with the property that each entry has at least one neighboring digit identical with it? Good examples are 110000111000, 001100111000, 111110000000.

My attempts:

How many strings are there?

We cannot tell the zeros and the ones apart, so using the multinomial coefficient, there are $\displaystyle\frac{12!}{7!5!}=792$ strings.

How many of them have no two consecutive zeros?

Group the zeros into groups of 2. So we have to arrange: 00,00,00,0,1,1,1,1,1

We have 9 elements to arrange and we cannot distinguish the three groups of 00 and the five ones. So there are $\displaystyle\frac{9!}{3!5!}=504$ strings that contain two consecutive zeros.

So there are $792-504=288$ strings.

How many have at least three ones among the first four entries?

Case $1$: 3 ones in the first four entries

Step $1$: Place 3 ones in the first four entries: $1$ way

Step $2$: Place a zero in the fourth entry: $1$ way

Step $3$: Arrange $1,1,0,0,0,0,0,0$: $\displaystyle\frac{8!}{2!6!}=28$ ways

Case $2$: $4$ ones in the first four entries

Step $1$: Place $4$ ones in the first four entries

Step $2$: Arrange remaining one and seven zeros: $\displaystyle\frac{8!}{7!}=8$ strings

So there are $28+8=36$ strings.

How many do not contain the substring $0000$?

Arrange $0000,0,0,0,1,1,1,1,1$

$\displaystyle\frac{9!}{3!5!}=504$ strings containing $0000$

So there are $792-504=288$ strings that do not contain $0000$.

How many strings are there with the property that each entry has at least one neighboring digit identical with it? Good examples are 110000111000, 001100111000, 111110000000.

I am stuck on this part.

Answer 1

To start off, let me help you fix some mistakes.

For (b) there are no ways to create such a string, so I don't know what happened there.

For (c) there is more than one way to place three ones in the first four slots. This should be an easy fix.

For (d) you are counting for example 100000101011 twice. (1 0000 0 1 0 1 0 1 1 = 1 0 0000 1 0 1 0 1 1) You can fix this by considering two cases: the string starts with 0000 or it does not. The first case is pretty easy. For the second case, you can consider permuting 10000 with four ones and three zeroes.

For (e) I admit I don't have an elegant solution. You can consider two cases again: the five ones are together or they are not. The first case is pretty easy. For the second case you have a bunch of two ones and a bunch of three ones. You could first consider the case where the string either starts or ends with a one, there are only a few options there. For the other case, the string starts and ends with a zero, and the remaining is permuting 0110 with 01110 and the last 0.

Answer 2

How many binary strings of length $12$ consist of seven zeros and five ones?

Your answer is correct.

How many binary strings of length $12$ consisting of seven zeros and five ones have no two consecutive zeros?

Place the seven zeros in a row.
$$0 \square 0 \square 0 \square 0 \square 0 \square 0 \square 0$$ If no two of them are consecutive, each of the six spaces between successive zeros must be filled with a one. Since there are only five ones, this is impossible. Thus, there are no such sequences.

How many binary strings of length $12$ consisting of seven zeros and five ones have at least three ones among the first four entries?

As you observed, such strings must either have three or four ones among the first four entries.

You counted the case in which all four of the first entries are ones correctly.

For the case in which exactly three of the first four entries are ones, choose three of the four positions for the ones. Since the other position among the first four entries must be a zero, that leaves six zeros and two ones for the last eight positions. Choose two of these eight positions for the ones. Hence, the number of sequences with exactly three ones in the first four positions is $$\binom{4}{3}\binom{8}{2}$$

Hence, the number of strings with at least three ones in the first four entries is $$\binom{4}{3}\binom{8}{2} + \binom{8}{1}$$

How many binary strings of length $12$ consisting of seven zeros and five ones do not contain the substring $0000$?

You showed that there are $\binom{12}{7}$ strings of length $12$ consisting of seven zeros and five ones. From these, we must subtract those strings in which the substring $0000$ appears.

You counted such substrings by arranging the block $0000$, the other three zeros, and the five ones. These nine objects can be arranged in $$\binom{9}{1}\binom{8}{3}\binom{5}{5} = \binom{9}{1}\binom{8}{3}$$ ways.

However, if we subtract this number from the total, we will have subtracted those strings in which there are two $0000$ substrings twice, once for each way we could designate one of those substrings as the substring $0000$. We only want to subtract such strings once. Thus, we must add them back.

Notice that since there are a total of seven zeros, it is not possible to have two disjoint substrings of the form $0000$. Thus, to have two such substrings, we must have a block of five consecutive zeros. The two substrings of the form $0000$ are the first four and last four of these five zeros. We now have eight objects to arrange, $00000$, the other two zeros, and the five ones. They can be arranged in $$\binom{8}{1}\binom{7}{2}\binom{5}{5} = \binom{8}{1}\binom{7}{2}$$ ways.

If we first subtract the number of strings with the block $0000$ and then add the number of substrings with two blocks of $0000$, we will not have subtracted those substrings with three blocks of $0000$ at all. That is because we subtract such substrings three times, once for each way we could designate one of those substrings as the substring $0000$, and add them three times, once for each of the $\binom{3}{2}$ ways we could designate two of the substrings as the blocks of four consecutive zeros. Therefore, we must subtract the number of substrings with three blocks of the form $0000$.

For three blocks of $0000$ to occur, we must have the block of six consecutive zeros $000000$ in the string. The three blocks of $0000$ start in the first, second, and third positions of this block. We have seven objects to arrange, $000000$, the other zero, and the five ones. The objects can be arranged in $$\binom{7}{1}\binom{6}{1}\binom{5}{5} = \binom{7}{1}\binom{6}{1}$$ ways.

If we subtract the number of strings that include the block $000000$, we will have subtracted too much. This is because we subtracted strings with four blocks of the form $0000$ four times, once for each way we could designate one of them as the block of the form $0000$, added them six times, once for each of the $\binom{4}{2} = 6$ ways we could designate two of them as the blocks of the form $0000$, and subtracted them four times, once for each of the $\binom{4}{3} = 4$ ways we could designate three of the blocks as the blocks of the form $0000$. We only want to subtract such strings once, so we must add them back.

A string with four blocks of the form $0000$ must contain seven consecutive zeros. We have six objects to arrange, the block and the five ones. They can be arranged in $$\binom{6}{1}\binom{5}{5} = \binom{6}{1}$$ ways.

By the Inclusion-Exclusion Principle, the number of strings that do not contain the substring $0000$ is $$\binom{12}{7} - \binom{9}{1}\binom{8}{3} + \binom{8}{1}\binom{7}{2} - \binom{7}{1}\binom{6}{1} + \binom{6}{1}$$

How many binary strings of length $12$ consisting of seven zeros and five ones do are there in which each digit has an identical digit adjacent to it?

This event will occur unless all the zeros are separated, which we showed is impossible, or all the ones are separated. Therefore, the answer can be found by subtracting the number of arrangements in which the ones are separated from the total number of arrangements. We can do this by placing the seven zeros in a row, which creates eight spaces in which we can place a one. $$\square 0 \square 0 \square 0 \square 0 \square 0 \square 0 \square 0 \square$$ To ensure that the ones are separated, we must choose five of these spaces for the ones, which can be done in $$\binom{8}{5}$$ ways.

Hence, the number of admissible arrangements is $$\binom{12}{7} - \binom{8}{5}$$