Question

An n-bit binary string is a sequence of length n over the alphabet {0,1}.

1. How many n-bit binary strings are there?
2. How many n-bit binary strings b1,…,bn are there such that b1b2≠00? In other words, how many n-bit binary strings don't begin with 00?
3. How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and b2b3≠11?
4. How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and such that b2b3≠01?

Answer 1

An -bit binary string is a sequence of length over the alphabet .

First Question: ( How many n-bit binary strings are there?)

The first term of an -bit binary string (a sequence of length ) can be filled by ways.

The second term of an -bit binary string (a sequence of length ) can be filled by ways.

The third term of an -bit binary string (a sequence of length ) can be filled by ways.

and so on upto th term of an -bit binary string (a sequence of length ) can be filled by ways.

Thus, there are -bit binary strings.        (Answer)

Second Question: ( How many -bit binary strings are there such that ? In other words, how many -bit binary strings don't begin with 00? )

The number of -bit binary strings such that is equal to

To calculate the number of -bit binary strings such that we fix and rest places can be filled by either or each. That means each places have two options.

Thus,

.

Therefore,

the number of -bit binary strings such that is equal to

.

Thus, there are number of -bit binary strings such that .         (Answer)

Third Question: ( How many -bit binary strings are there such that and ? )

Number possible ways to fill are, .

But for our case, cases are not possible since our requirement is and .

Thus there are remaining four cases .

And the rest places can be filled by either or each. That means each places have two options.

Thus,

There are -bit binary strings such that and .         (Answer)

Fourth Question: ( How many -bit binary strings are there such that and such that ? )

Number possible ways to fill are, .

But for our case, cases are not possible since our requirement is and .

Thus there are remaining five cases .

And the rest places can be filled by either or each. That means each places have two options.

Thus,

There are -bit binary strings such that and .         (Answer)