Combinatorics with binary strings

Question

a) I'm currently trying to find how many binary strings of length 10 have at least one 1 and one 0, and I've concluded that this is $2^{10} - 2$. This is because the only strings that violate the condition are 1111111111 (ten 1's), and 0000000000 (ten 0's).

b) For a binary string with exactly five 1's or begins with a 0, I currently have $10 \choose 5$ + $2^9$ - $9 \choose 5$. This is because we want to select 5 spots out of the 10 for exactly five 1's, and then add that with how many strings can start with a 0, and the subtract $9 \choose 5$, which is how many strings begin with a 0 and have exactly five 1's.

c)A binary string has 01010101 appearing somewhere in the string. This is the only one I have no idea how to approach. I understand 01010101 can appear in three positions in the binary string of length 10 (front, middle, and end), but I have no idea how to combine all of these, or what to exclude.

d)There are five 1's in the string or it has an even amount of 1's in the string. A string with five 1's would be $ 10 \choose 5$, and a string with would be $ 10 \choose 2$, $ 10 \choose 4$, $ 10 \choose 6$, $ 10 \choose 8$, and $ 10 \choose 10$. So can I use the sum rule to combine all of these or is there an easier way?

Is my thinking for these problems correct?

Answer 1

For part c), we can think of 01010101 as another string S. Because we cannot have S appear twice, we are looking for all binary strings of length 3 with one S. Then, we simply have $3\cdot2^2$ possible strings because for each of the 3 positions of S there are $2^2$ other binary strings of length 2.

The only case where it overcounts is (I believe) S01 = 01S. All binary strings xSx is different from Sxx and xxS because the third element of xSx must be a 0 while the third element of the latter two must be a 1. But for the latter two to the the same, S01 = 01S (because the first, second, second last and last characters must be 01 to match S) and therefore we have only overcounted once.

Hence our final answer is $3\cdot2^2 - 1$.

Answer 2

To explain the answer further, let us treat our universal set, $U$, as all binary strings of length 10. By theorem or earlier example, we know that there are $2^{10}$ different such strings (seen easily by multiplication principle).

The negation of the phrase "at least one $1$ and at least one $0$" is:

no $1$'s or no $0$'s

Noting that there is no overlap between those cases, this leads us to discover that we may partition our universal set into the following three disjoint sets:

• $A$: There are no $1$'s (only possibility is then $000~000~000~0$)
• $B$: There are no $0$'s (only possibility is then $111~111~111~1$)
• $C$: There is at least one $1$ and at least one $0$

As these form a partition (i.e. $A\cup B\cup C = U$ and $A\cap B = A\cap C=B\cap C = \emptyset$), we know that $|A|+|B|+|C|=|U|$

so:

$$2^{10} = |U| = |A|+|B|+|C|=1+1+|C|$$

and

$$|C| = 2^{10}-2$$

Answer 3

More generally the number of $n$ bit strings with at least $k$ zeroes and $j$ ones is $$ 2^n-\sum_{0\leq m \leq k-1} C_m^n - \sum_{0\leq m \leq j-1} C_m^n $$ where $C_m^n$ is the binomial coefficient, provided $j+k\leq n.$