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!

The answer supplied by Gerry might be correct, but the math to solve that equation is a bit beyond me. In the end, I gave up and used inclusion :)
I take the number of words of length L and visualize the space between each word as a box.
I then calculate all the ways that I can place one ball (representing the letter A) in these boxes, with the constraint of only placing one ball per box max (Duplicate balls would mean adjacent AA). This is achieved by calculating C(balls, boxes). Finally since each box, can represent any letter of the alphabet (Except A) I multiply this result by the number of possible box permutations.
C(balls,boxes)*(number of letters -1)^boxes;
My end result is the sum of the above equation solving for (balls = 0, boxes=lenghtOfWord ;  balls = boxes; balls++ , boxes-- ).
MY programmatic solution:
int k = 10;
int n = 2;

double res = 0;

int balls = 0; int boxes = n;
while(balls<=boxes){
    res += comb(boxes,balls)*Math.pow(k-1,boxes); 
    balls++;
    boxes--;
}

