# N letter words

1. Feb 23, 2006

### heman

How many n-letter words can be written with A,B,C without placing two A's

will this question involve some kind of genereating function....if not,,how to do it?

2. Feb 23, 2006

### matt grime

You can do it as a difference equation.

Let w(n) be the number words with no repeated A's of length n.

any such can start with a B or C and be followed by any other word of n-1 letters with no repeated As, thus

w(n)=2w(n-1)+no. of words starting with A.

how many words start with A? Well, the next letter can be either B or C, then there is any of the words of length n-2 with no repeated As, thus

w(n)=2w(n-1)+2w(n-2)

subject to the initial conditions w(1)=1, w(2)=8 (3 choices of first letter, 3 of second, minus the one double A choice).

3. Feb 23, 2006

### heman

just bit more insight ...the first equation is not clear,,

4. Feb 23, 2006

### heman

just bit more insight ...the first equation is not clear,,

5. Feb 23, 2006

### matt grime

yes it is. think about it. I've just 'counted the possibilities'

6. Feb 23, 2006

### heman

its done..Thanks Matt.