Results 1 to 10 of 10

Math Help - Recurrence Relation for a binary string

  1. #1
    Newbie
    Joined
    Mar 2010
    Posts
    4

    Recurrence Relation for a binary string

    an is the number of strings of length n in which every 0 is immediately followed by at least two consecutive 1's. Example: the string 101111 is allowed, but 01110 is not.
    so what the problem asks for is to find a recurrence relation
    and initial conditions for an. now i had something going where:
    if it starts with a 011, that would be an-3
    starts with a 1, it could be 1011_________ = an-4, or 11011_____ = an-5, .....etc (where ____ could be 0 or 1)

    i was just wondering if this is the right approach? and how to also figure in the possibility of another zero appearing somewhere along the string of _____.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1578
    Awards
    1
    First find the first three.
    A_1:\{1\},~~a_1=1
    A_2:\{11\},~~a_2=1
    A_3:\{011,111\},~~a_3=2
    Note that no string in A_n can end in a zero.
    If you add a 1 to the right end of any string in A_3 you have a valid string in A_4.
    What is the complete list for A_4?
    That is a way to proceed.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2010
    Posts
    4
    alright so A4 = {1011,0111,1111} = 3, A5 = {10111,01111,11111,11011}...etc

    but how would i write this as a recurrance relation for an = ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1578
    Awards
    1
    Quote Originally Posted by Math101 View Post
    alright so A4 = {1011,0111,1111} = 3, A5 = {10111,01111,11111,11011}...etc
    but how would i write this as a recurrance relation for an = ?
    Well that is for you to work on.
    Here are more hints.
    Any valid string must the last three \cdots 011\text{ or }\cdots 111.
    It is safe to add a 1 to any string in A_{n-1}.
    BUT that does not get all in A_n.
    What else does? Be careful do not get repeats.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2010
    Posts
    4
    alright so what i figured out for an is the following:
    an = an-1 + (0.5 * an-1) + an-2 + (0.5* an-2) + ...a2 + (0.5 * a2) + a1.

    where each (0.5 * an__) is rounded up. This is because to get lets say a5, you can add 1 to the end of every string in a4, and add also add 1 to the start of the string in a4 that starts with a 10.
    so a4 = {0111,1111,1011}, and a5 = {01111,11111,10111,11011}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1578
    Awards
    1
    Quote Originally Posted by Math101 View Post
    alright so what i figured out for an is the following:
    an = an-1 + (0.5 * an-1) + an-2 + (0.5* an-2) + ...a2 + (0.5 * a2) + a1.
    Actually it should be a_n=a_{n-1}+a_{n-3}.
    We add 1 to the end of every string in  A_{n-1} and add 011 to the end each string in  A_{n-3} .
    You should try that to see why it works with the A_nís we already have.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2010
    Posts
    2
    "Actually it should be ."

    I don't think that is correct.
    if a(5)=4, a(3)=2

    a(6) = a(5) + a(3) = 6

    but:
    a(6): {111111,101111,110111,111011,011111} = 5

    Isn't it something like:
    a(n) = a(n-1) +1 with initial conditions a(0)=a(1)=a(2)=1
    where n >=3. I am not sure if this is a valid way of stating a recurrence relation though...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1578
    Awards
    1
    Quote Originally Posted by jones357 View Post
    a(6) = a(5) + a(3) = 6
    but: a(6): {111111,101111,110111,111011,011111} = 5
    But you missed one in A_6=\{111111,101111,110111,111011,011111,{\color{b  lue}011011}\}
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Mar 2010
    Posts
    2
    I had misunderstood the original question to mean that after a 0, there must be all 1's of which there must be at least 2.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1578
    Awards
    1
    Quote Originally Posted by jones357 View Post
    there must be all 1's of which there must be at least 2.
    "every 0 is immediately followed by at least two consecutive 1's." does not mean that.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. form a binary string
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 22nd 2009, 11:11 PM
  2. binary string probability question
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: June 1st 2008, 07:56 PM
  3. Binary relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 3rd 2008, 11:58 AM
  4. binary relation
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 24th 2008, 10:34 AM
  5. [SOLVED] [SOLVED] recurrence relation for full binary tree
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 15th 2007, 02:36 PM

Search Tags


/mathhelpforum @mathhelpforum