Counting words with subset restrictions I have an alphabet of N letters {A,B,C,D...N} and would like to count how many L-length words do not contain the pattern AA.
I've been going at this all day, but continue to stumble on the same problem.
My first approach was to count all possible combinations, (N^L) and subtract the words that contain the pattern.
I tried to count the number of ways in which I can place 'AA' in L boxes, but I realized early on that I was double counting, since some words can contain the pattern more than once.
I figured that if I had a defined length for the words and the set, I could do it by inclusion/exclusion, but I would like to arrive at a general answer to the problem.
My gut feeling is that somehow I could overcount, and then find a common factor to weed out the duplicates, but I can't quite see how.
Any help would be appreciated!

Call the answer $x_L$. 
Then $x_L=Nx_{L-1}-y_{L-1}$, where $y_L$ is the number of allowable words of length $L$ ending in $A$. 
And $y_L=x_{L-1}-y_{L-1}$. 
Putting these together we get $Nx_L-x_{L+1}=x_{L-1}-(Nx_{L-1}-x_L)$, which rearranges to $x_{L+1}=(N-1)x_L+(N-1)x_{L-1}$. 
Now: do you know how to solve homogeneous constant coefficient linear recurrences? 
EDIT. If all you want is to find the answer for some particular values of $L$ and $N$ then, as leonbloy notes in a comment to your answer, you can use the recurrence to do that. You start with $x_0=1$ (the "empty word") and $x_1=N$ and then you can calculate $x_2,x_3,\dots,x_L$ one at a time from the formula, $x_{L+1}=(N-1)x_L+(N-1)x_{L-1}$. 
On the other hand, if what you want is single formula for $x_L$ as a function of $L$ and $N$, it goes like this: 
First, consider the quadratic equation $z^2-(N-1)z-(N-1)=0$. Use the quadratic formula to find the two solutions; I will call them $r$ and $s$ because I'm too lazy to write them out. 
Now it is known that the formula for $x_L$ is $$x_L=Ar^L+Bs^L$$ for some numbers $A$ and $B$. If we let $L=0$ and then $L=1$ we get the system $$\eqalign{1&=A+B\cr N&=rA+sB\cr}$$ a system of two equations for the two unknowns $A$ and $B$. So you solve that system for $A$ and $B$, and then you have your formula for $x_L$. 
