Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Ternary String recursion relation

  1. Apr 17, 2010 #1
    I don't understand this at all I have the solution but no idea.

    I am suppose to find the recursion relation for consecutive 0 in a ternary string(String that contains only 0, 1 and 2)

    So the solution I have is :

    Strings starting with 1 = an(The n is the small n for recursion) - 1
    Strings startring with 2 = an - 1
    Strings starting with 01 = an - 2
    Strings starting with 02 = an - 2
    Strings starting with 00 = 3^n-2

    So the relation is an = 2an-1 + 2an - 2 + 3^n-2 for n >= 3

    So how did they get the relation?

    Why an - 1? What is the length of the String they base their calculations on?

    Example :

    I take Strings starting with 1, I can have 10, 11, 12, why an - 1? and not an - 3, all 3 do not have consecutive 0s?

    Or if I take the length of the String as 3, I can have 100, 110, 101, 102, 111.... so why -1? When I have so many other strings to minus off?

    And also for 00,

    Where did the 3^n come from?

    This is so mind confusing.
     
  2. jcsd
  3. Apr 17, 2010 #2
    I think you misunderstand what the equations say. The idea is that we let [itex]a_n[/itex] be the number of ternary strings of length n with 00 as a substring. Now if we have a string of length n starting with 1, then it contains consecutive 0 iff the remaining (n-1) characters do. Thus the number of such strings having consecutive 0s is equal to the number of strings of length (n-1) having consecutive 0s, i.e. [itex]a_{n-1}[/itex] (which you wrote as an-1). Similar reasoning holds for the remaining cases. Note that the number of such strings starting with 00 is:
    [tex]3^{n-2}[/tex]
    I think you may have interpreted the results as [itex]a_n-1[/itex] and [itex]3^n-2[/itex] which is incorrect.
     
  4. Apr 17, 2010 #3
    Hey wait... even if you say that n - 1 is because iff the consective string is 00... but what if the consecutive string is not 00? it doesn't take that into account?

    Okie, but I don't understand why is it for 00 it is [tex]3^{n-2}[/tex]
     
    Last edited: Apr 17, 2010
  5. Apr 18, 2010 #4
    I'm not sure exactly what you mean here. Could you elaborate? We are always looking for consequtive 0s (i.e. for 00).

    [itex]3^{n-2}[/itex] is the number of ternary strings of length (n-2). If we know the string starts with 00 we just want the last (n-2) characters to be arbitrary.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook