Purchase Solution

n-Bit Binary Strings with Fixed Digits

Not what you're looking for?

Ask Custom Question

I need to show that the number of n-bit binary strings that contain exactly two occurrences of 10 is C(n+1, 5).

Purchase this Solution
Solution Summary

It is shown how it may be proven that the number of n-bit binary strings that contain exactly two occurrences of 10 is C(n+1, 5).

Solution Preview

Let's look at the number of ways to do this:

It's good to start with a simple example to gain insight into how the problem will work. For example, take some number of length n:

1010xxxxxx...... where the x's are the numbers which could be anything. We already have the two exaples of the '10', so no more can appear in the latter string of numbers.

So, if we have a string of length m, how many possible values are there which *don't* include 10? Well, once we place a '1' in the number, it can't be followed by any '0's, so they will be like:

11111.....
01111....
00111.....
00011....
.
.
00000...

Get the idea? If the string is of length m, then this means there are m+1 different ways to do it. Again, this is only when you can't have 10 ...

Purchase this Solution
Free BrainMass Quizzes
Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

View More Free Quizzes
Related BrainMass Solutions

  • Why Hexadecimal, Octal and Binary?

    Computers have been designed with various word sizes of: 36, 48, or 60 bits. The number of possible combinations of a group of N bits is 2^N = 2x2x2 ... x2 (N 2s).

  • Automata and Computability

    Let addn: {0,1}2n{0,1}n+1 take the sum of two n bit binary integers and produce the n + 1 bit result. Show that we can compute the addn function with 0(n) size circuits. See attached file for full problem description.

  • Evaluate Bit Strings

    If a bit string is N bit wide, there are (2 ^N) / 2 strings which bein with 0 or end with a 1. 2^N /2 can also be expressed as 2^ (N-1) So in case of a strings of length, the answer is 2^(6-1) = 32 3.

  • Bit Strings

    So the total number of bit strings of length 6 which begin with a 0 and end with a zero is 2^4 = 16 (c) The second to the fourth digits can be filled in 2 ways, by either a zero or a one.

  • Induction Proof : Strings of Digits

    25320 Induction Proof: Strings of Digits If n >= 1, the number of strings using the digits 0,1, and 2 with no two consecutive places holding the same digit, is 3x2^n-1.

  • Data Conversion (8-bits to decimal)

    If the last two digits of a 2's complement binary number are 00 (e.g., the binary number 01100), what does that tell you about the number?

  • Recurrence relations - initial conditions

    Then the number of bit strings of length n - 3 which do not contain three consecutive 0s (and therefore the number of bit strings of length n + 1 containing three consecutive 0s exactly at the end) is 2^(n-3) - a_(n-3) .

  • Conversion of Binary number to Decimal number

    The program will read the binary number (eight binary digits on one line with no spaces between them), convert the number, then go back to the data file to retrieve the next number.

  • binary, numbers, fraction, decimal, step

    113365 binary, numbers, fraction, decimal, step What is the result of adding the following two positive binary bit strings?

View More Related Solutions