Results 1 to 3 of 3

Math Help - Recurrence of a Ternary Sequence

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    18

    Recurrence of a Ternary Sequence

    (a) A ternary sequence is one in which each element is 0, 1, or 2. Complete the following argument to find a recurrence relation and initial
    conditions for t_n the number of ternary sequences of length n that do not contain 012:
    First, t_0 = 1; t_1 = 3; and t_2 = 9 because ....
    To obtain a recursion, let n \geq 3 and focus on the first element of the sequence. There are two cases depending on whether it equals zero.
    If the first element is not zero, then ...
    If the first element is zero then the number of sequences without 012 equals 1 * t_{n-1} minus the number of ternary sequences of length n that start 012 but do not have it appearing later in the sequence, which is ... The subtraction is because ... . Hence, for n \geq 3; t_n =... which, after simplifying,
    gives the recurrence tn = 3*t_{n-1} - t_{n-3}.


    (b) Find a recurrence relation and initial conditions for c_n, the number of sequences of length n of upper case letters that do not contain GOAL.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Celcius View Post

    (b) Find a recurrence relation and initial conditions for c_n, the number of sequences of length n of upper case letters that do not contain GOAL.
    In order? So, clearly G,O,A,L,B would not be included, but what about G,O,B,A,L?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    18
    Quote Originally Posted by Drexel28 View Post
    In order? So, clearly G,O,A,L,B would not be included, but what about G,O,B,A,L?
    Thanks for your response. From my understanding, G O B A L is allowed. The letters must be in order and together.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Logistsic Recurrence Sequence
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 24th 2011, 08:54 AM
  2. Linear second order recurrence sequence
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: March 28th 2011, 01:46 PM
  3. Recurrence and Fibonacci sequence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 12th 2010, 08:27 PM
  4. recurrence sequence
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: October 30th 2008, 04:02 AM
  5. Ternary sequence
    Posted in the Statistics Forum
    Replies: 2
    Last Post: April 30th 2007, 01:14 PM

Search Tags


/mathhelpforum @mathhelpforum