Results 1 to 2 of 2

Math Help - Derive a formula

  1. #1
    Newbie
    Joined
    Dec 2006
    Posts
    23

    Derive a formula

    Hi
    Could anyone help me with that problem:

    A bit string is a string over the alphabet {0,1}. Let n be a natural number. Derive a formula for the number of bit strings of length 2n that contain 01 as a substring. Explain your answer clearly.

    Thx
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by mauro21pl View Post
    Hi
    Could anyone help me with that problem:

    A bit string is a string over the alphabet {0,1}. Let n be a natural number. Derive a formula for the number of bit strings of length 2n that contain 01 as a substring. Explain your answer clearly.
    The total number of strings of length n is 2^n. We must subtract from that the number of strings that do not contain 01 as a substring.

    But if a string does not contain 01 then it must never have a 0 followed by a 1. So all the 1s must come at the beginning of the string, followed by all the 0s, like 111...100...0. There are n+1 such strings of length n. The formula is therefore 2^n-n-1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Derive a power reduction formula
    Posted in the Calculus Forum
    Replies: 2
    Last Post: February 6th 2011, 05:02 PM
  2. need to derive a formula
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: September 1st 2010, 06:20 PM
  3. Replies: 2
    Last Post: March 6th 2009, 06:36 AM
  4. Derive the Cubic formula
    Posted in the Algebra Forum
    Replies: 10
    Last Post: April 20th 2008, 09:32 AM
  5. [SOLVED] How to derive sum of cubes formula?
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: November 30th 2005, 01:51 PM

Search Tags


/mathhelpforum @mathhelpforum