Writing N-Letter Words with A, B, and C | Avoiding Repeated A's in Combinations

[heman]

How many n-letter words can be written with A,B,C without placing two A's
adjacent to each other?

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

 

[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).

 

[heman]

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

 

[heman]

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

 

[matt grime]

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

 

[heman]

its done..Thanks Matt.