• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

### Select your language

Suggested languages for you:

Americas

Europe

Q20E

Expert-verified
Found in: Page 413

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

### Answers without the blur.

Just sign up for free and you're in.

# How many bit strings of length $${\bf{10}}$$ havea) exactly three $$0s$$?b) more $$0s$$ than $$1s$$ ?c) at least seven $$1s$$ ?d) at least three $$1s$$ ?

a) The bit string of length $$10$$ having exactly three $$0's$$is $$120$$.

b) The bit string of length $$10$$ having more $$0's$$than $$1's$$is $$386$$.

c) The bit string of length $$10$$ having at least seven $$1's$$is $$176$$.

d) The bit string of length $$10$$ having at least three $$1's$$is $$968$$.

See the step by step solution

## Step 1: Given data

Length of bit string $$= 10$$

## Step 2: Concept of Combination

A combination is a selection of items from a set that has distinct members.

Formula:

$$_n{C_r} = \frac{{n!}}{{r!(n - r)!}}$$

## Step 3: Calculation for the bit string for exactly three $$0's$$

a)

Find the bit string of length $$10$$ having exactly three $$0's$$, use the formula of combination.

Number of possible outcomes $$= C(10,3)$$

$$\begin{array}{l}C(10,3) = \frac{{10!}}{{3!(10 - 3)!}}\\C(10,3) = \frac{{10!}}{{3!7!}}\end{array}$$

Simplify the factorial of the above expression:

$$\begin{array}{l}C(10,3) = \frac{{10 \times 9 \times 8 \times 7!}}{{3 \times 2 \times 1 \times 7!}}\\C(10,3) = \frac{{10 \times 9 \times 8}}{{3 \times 2 \times 1}}\\C(10,3) = 120\end{array}$$

Hence, the bit string of length 10 having exactly three $$0's$$is $$120$$ .

## Step 4: Calculation for the bit string for more $$0's$$than $$1's$$

b)

Find the bit string of length $$10$$ having more $$0's$$ than $$1's$$, when less than$$5$$bits are $$0's$$, use the formula of combination.

Number of possible outcomes $$\; = C(10,4) + C(10,3) + C(10,2) + C(10,1)$$

$$\begin{array}{l}C(10,4) + C(10,3) + C(10,2) + C(10,1) + C(10,0) = \left( {\frac{{10!}}{{4!(10 - 4)!}} + \frac{{10!}}{{3!(10 - 3)!}} + \frac{{10!}}{{2!(10 - 2)!}} + \frac{{10!}}{{1!(10 - 1)!}} + \frac{{10!}}{{0!(10 - 0)!}}} \right)\\C(10,4) + C(10,3) + C(10,2) + C(10,1) + C(10,0) = \frac{{10!}}{{4!6!}} + \frac{{10!}}{{3!7!}} + \frac{{10!}}{{2!8!}} + \frac{{10!}}{{1!9!}} + \frac{{10!}}{{0!10!}}\end{array}$$

Simplify the factorial of the above expression:

$$\begin{array}{l}C(10,4) + C(10,3) + C(10,2) + C(10,1) + C(10,0) = 210 + 120 + 45 + 10 + 1\\C(10,4) + C(10,3) + C(10,2) + C(10,1) + C(10,0) = 386\end{array}$$

Hence, the bit string of length 10 having more $$0's$$ than $$1's$$is $$386$$.

## Step 5: Calculation for the bit string for at least seven \(1's\]

c)

Find the bit string of length \(10\] having at least seven \(1's\], use the formula of combination.

The bit string of length 10 having at least seven \(1's\] is same as the bit string of length \(10\] having at most three \(0's\].

Number of possible outcomes \( = C(10,3) + C(10,2) + C(10,1) + C(10,0)\]

\(\begin{array}{l}C(10,3) + C(10,2) + C(10,1) + C(10,0) = \frac{{10!}}{{3!(10 - 3)!}} + \frac{{10!}}{{2!(10 - 2)!}} + \frac{{10!}}{{1!(10 - 1)!}} + \frac{{10!}}{{0!(10 - 0)!}}\\C(10,3) + C(10,2) + C(10,1) + C(10,0) = \frac{{10!}}{{3!7!}} + \frac{{10!}}{{2!8!}} + \frac{{10!}}{{1!9!}} + \frac{{10!}}{{0!10!}}\end{array}\]

Simplify the factorial of the above expression:

\(\begin{array}{l}C(10,3) + C(10,2) + C(10,1) + C(10,0) = 120 + 45 + 10 + 1\\C(10,3) + C(10,2) + C(10,1) + C(10,0) = 176\end{array}\]

Hence, the bit string of length 10 having at least seven \(1's\] is \(176\].

## Step 6: Calculation for the bit string for at least three \(1's\]

d)

Find the bit string of length \(10\] having at least three \(1's\], use the formula of combination.

Number of possible outcomes\( = C(10,3) + C(10,4) + C(10,5) + C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10)\]

\(\begin{array}{l}C(10,3) + C(10,4) + C(10,5) + C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10) = \left( {\begin{array}{*{20}{l}}{\frac{{10!}}{{3!(10 - 3)!}} + \frac{{10!}}{{4!(10 - 4)!}} + \frac{{10!}}{{5!(10 - 5)!}} + \frac{{10!}}{{6!(10 - 6)!}}}\\{ + \frac{{10!}}{{7!(10 - 7)!}} + \frac{{10!}}{{8!(10 - 8)!}} + \frac{{10!}}{{9!(10 - 9)!}} + \frac{{10!}}{{10!(10 - 10)!}}}\end{array}} \right]\\C(10,3) + C(10,4) + C(10,5) + C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10) = \frac{{10!}}{{3!7!}} + \frac{{10!}}{{4!6!}} + \frac{{10!}}{{5!5!}} + \frac{{10!}}{{6!4!}} + \frac{{10!}}{{7!3!}} + \frac{{10!}}{{8!2!}} + \frac{{10!}}{{9!1!}} + \frac{{10!}}{{10!0!}}\end{array}\]

Simplify the factorial of the above expression:

\(\begin{array}{l}C(10,3) + C(10,4) + C(10,5) + C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10) = 120 + 210 + 252 + 210 + 120 + 45 + 10 + 1\\C(10,3) + C(10,4) + C(10,5) + C(10,6) + C(10,7) + C(10,8) + C(10,9) + C(10,10) = 968\end{array}\]

Hence, the bit string of length 10 having at least three \(1's\]is \(968\].

### Want to see more solutions like these?

Sign up for free to discover our expert answers

## Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.