Results 1 to 3 of 3

Math Help - recurrence relations

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    8

    recurrence relations

    Find a recurrence relation for the number of ternary strings (0 s, 1 s and 2 s) of length n that contain none of the strings 101, 202, 102, or 201. What are the initial conditions? Use the recurrence to compute the number of such sequences of length 5.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Apr 2008
    Posts
    17
    To figure out the initial conditions, simply write out the ternary strings for n=1 and n=2:


    n=1

    0
    1
    2



    n=2

    00
    01
    02
    10
    11
    12
    20
    21
    22


    That should be sufficient for some initial conditions. I guess you could also do it for n=0, but there are 0 of length 0.

    From here, I would suggest writing out for maybe n=3 and n=4. Beyond that, you may want a computer to spit out such things. Then you could look for a pattern and find the recurrence. That's just a brute force sort of idea.


    For now, it's all I've got. We may need to think about this more mathematically, that is, what is the equation for the number of unrestricted ternary strings? Then, what is the mathematical restriction we wish to impose?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2008
    Posts
    8
    thank you for your help. I will greatly appreciate it.But I think the real problem starts form 3 itself. So, can you help me in finding the recurrence relation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 28th 2011, 03:50 PM
  2. Recurrence relations
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: February 24th 2011, 10:45 AM
  3. Recurrence relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 1st 2010, 07:59 AM
  4. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 08:56 PM
  5. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 11th 2008, 12:57 AM

Search Tags


/mathhelpforum @mathhelpforum