How many bit strings of length 10 contain:

/ Permutations and combinations / By

Let’s examine the first question.

How many bit strings of length 10 contain exactly four 1s?

From the question, you can see that the order of the four 1s does not matter. We just need to find out how many bit strings of length 10 contain exactly four 1s.

This reminds me of a definition.

“An r-combination of elements of a set is an unordered selection of r elements from the set. Thus, an r-combination is simply a subset of the set with r elements.”

Theorem: “The number of r-combinations of a set with n elements, where n is a nonnegative integer and r is an integer with 0 ≤ r ≤ n, equals C(n,r) =n! / r!(n−r)! ”

The previous definition and theorem are from the textbook Discrete Mathematics and its Applications by Rosen.

Now we have the definition and theorem we need to solve this type of exercise.

So, let’s get into it.

a) exactly four 1s?

In this case, we need to think a bit out of the box.

Remember that the beauty of mathematics is that most of the time (at least in the interest scenarios), the theory is simple but there is no algorithm that we can apply to solve exercises using that theory. We need to be creative.

Let’s go through some examples of such bit strings of length 10:

  1. 1111000000
  2. 0111100000
  3. 1010101000
  4. 0000001111

Looking at the examples above, we can see that the positions of the 1s form a 4-combination of the set {1,2,3,4,5,6,7,8,9,10}.

These are the combinations for the above examples:

  1. 1,2,3,4.
  2. 2,3,4,5.
  3. 1,3,4,7.
  4. 7,8,9,10.

So, the answer to this exercise is

C(10,4)=10!/4!(10-4)!=10!/4!6!=10*9*8*7*6!/4!6!= 10*9*8*7*/4!=5040/24=210.

Answer:

There are 210 bit strings of length 10 that contain exactly four 1s.

b) at most four 1s?

For the bit string to have at most four 1s, it can have exactly zero 1s, exactly one 1s, exactly two 1s, exactly three 1s, or exactly four 1s.

We will use the same approach as in the previous exercise. We will calculate the r-combinations formed by the positions of 1s.

So, we need to calculate each of the previous combinations and then we apply the sum rule.

As we already calculated C(10,4)=210 in the previous exercise, we will reuse it.

C(10,0)+C(10,1)+C(10,2)+C(10,3)+C(10,4)

= 1 + 10!/9! + 10!/2!8! + 10!/3!7! + 210

= 1 + 10*9!/9! + 10*9*8!/2!8! + 10*9*8*7!/3!7! + 210

= 1 + 10 90/2 + 10*9*8/6 +210

= 56 + 120 + 210

= 386

Answer:

There are 386 bit strings of length 10 that contain at most four 1s.

c) at least four 1s?

We continue to use the approach of calculating the 3-combinations on the set of the first 10 positive integers.

So, having at least four 1s means having four 1s, five 1s, six 1s, and so on until exactly ten 1s. Also, having at least four 1s is the same as having at most six 0s.

We already calculated in the previous exercises how many bit strings of length 10 have at most four 1s. It is evident that the number is the same for the bit strings of length 10 that have at most four 0s.

So, we just need to add the bit strings of length 10 that have exactly five and six 0s.

386 + C(10,5) + C(10,6)

= 386 + 10!/5!(10-5)! + 10!/6!(10-6)!

= 386 + 10*9*8*7*6*5!/5!5!+ 10*9*8*7*6!/6!4!

= 386 +10*9*8*7*6/5! + 10*9*8*7/4!

= 386 + 30240/120 + 5040/24

= 386 + 252 + 210

= 848

Answer:

There are 848 bit strings of length 10 that contain at least four 1s.

d) an equal number of 0s and 1s?

This is a similar case to exercise a). Notice that an equal number of 0s and 1s means exactly five 0s and five 1s.

Also, the positions of the five 0s will determine the position of the five 1s.

Because of this, the answer is the number of 5-combinations of the 10 elements.

C(10,5)

= 10!/5!(10-5)!

= 10*9*8*7*6*5!/5!5!

= 10*9*8*7*6/5!

=30240/120

=252

Answer:

There are 252 bit strings of length 10 that contain an equal number of 0s and 1s.

Related exercises: