Results 1 to 2 of 2

Math Help - Finding a recurrence relation

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    37

    Exclamation Finding a recurrence relation

    Define an n-letter word to be a string of n letters, each taken from the 26 letters of the alphabet. Find a recurrence relation for an, n >= 0, where an is the number of n-letter words in which no adjacent letters in the word can both be vowels. (For example, bark is such a 4-letter word, but meow is not.)
    Last edited by sbankica; November 25th 2009 at 08:55 PM. Reason: wrong symbol
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by sbankica View Post
    Define an n-letter word to be a string of n letters, each taken from the 26 letters of the alphabet. Find a recurrence relation for an, n >= 0, where an is the number of n-letter words in which no adjacent letters in the word can both be vowels. (For example, bark is such a 4-letter word, but meow is not.)
    Hint:

    Let's say we want to find a_{n+1}. For the sake of brevity, let's say a string is "acceptable" if it does not contain two adjacent vowels.

    Break the possibilities into two disjoint sets depending on whether the (n+1)-th letter is a vowel. The total number of possibilities is the sum of the sizes of these sets.

    If the (n+1)-th letter is a vowel, the preceding n letters can be any acceptable string which does not end in a vowel. If the nth letter is not a vowel, then the preceding n-1 letters can be any acceptable string, which can be done in a_{n-1} ways. Then how many choices are there for the nth and (n+1)-th letters?

    If the (n+1)-letter is not a vowel, then the preceding n letters can be any acceptable string, which can be done in a_n ways. Then how many choices are there for the (n+1)-th letter?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. finding recurrence relation - question #2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 26th 2009, 08:19 AM
  2. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 19th 2009, 03:57 AM
  3. Finding a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 18th 2008, 01:39 PM
  4. Replies: 1
    Last Post: October 24th 2008, 10:27 AM
  5. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2007, 06:54 PM

Search Tags


/mathhelpforum @mathhelpforum