Results 1 to 2 of 2

Math Help - Combinatorics help

  1. #1
    jake77
    Guest

    Combinatorics help

    Can anyone please help me with this question? I am having a little trouble with it so i would appreciate any help.

    For
    n less then 1, let w(n) be the number of words of length n in the alphabet {a, b, c, d, e} with no adjacent aís. Determine a recursive
    relation for
    w(n), with appropriate initial values. Your recursion MUST
    BE
    accompanied by a combinatorial proof of the result, however, you DO
    NOT NEED
    to find a closed form for w(n).

    Thansk and I appreciate it.

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    You mean n greater than 1 (n less than 1 makes no sense).

    Well, for n = 2, w(2) = 5^2-1 (since all words are possible except aa).

    For n > 2, first find the number of n-letter words beginning with a. The second letter must be b, c, d or e. The number of n-letter words beginning with ab is w(n−2). This is also the number of n-letter words beginning with ac, ad or ae. Hence the total number of n-letter words beginning with a is 4w(n−2).

    The number n-letter words beginning with b is w(n−1). This is also the number of n-letter words beginning with c, d or e. Hence the total number of n-letter words not beginning with a is 4w(n−1).

    Therefore, the recurrence relation is w(1) = 5, w(2) = 24 and w(n) = 4[w(n−1)+w(n−2)] for n > 2.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Combinatorics.
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: July 20th 2010, 02:29 AM
  2. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 18th 2010, 08:14 PM
  3. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 3rd 2010, 05:24 PM
  4. combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 1st 2010, 10:53 PM
  5. Combinatorics
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2009, 06:03 AM

/mathhelpforum @mathhelpforum