Results 1 to 2 of 2

Math Help - Counting Strings

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    21

    Counting Strings

    Let a_n be the number of strings of length n in which every 0 is immediately followed by three consecutive 1's. So for example, the string 101111 is allowed but 01110 is not.

    Find a recurrence relation and initial conditions for a_n.

    I know the first initial condition has to have 4 places because the 0 need three 1's after it. From there I am lost.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by minkyboodle View Post
    Let a_n be the number of strings of length n in which every 0 is immediately followed by three consecutive 1's. So for example, the string 101111 is allowed but 01110 is not.

    Find a recurrence relation and initial conditions for a_n.

    I know the first initial condition has to have 4 places because the 0 need three 1's after it. From there I am lost.
    How about a(n)=a(n-4)+a(n-1)

    a1=1
    a2=1
    a3=1
    a4=2

    Break up a(n) in two cases - starting with 0 and staring with 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How many eight-bit strings contain exactly three 0's
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 4th 2010, 09:06 AM
  2. advanced counting: bit strings with 2x '00'
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 13th 2009, 05:43 PM
  3. Replies: 12
    Last Post: May 15th 2009, 05:41 PM
  4. Bit strings
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2009, 12:07 PM
  5. strings
    Posted in the Statistics Forum
    Replies: 10
    Last Post: January 17th 2009, 01:35 PM

Search Tags


/mathhelpforum @mathhelpforum