# Thread: Combinatorics help

1. ## 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.

2. 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.