1
$\begingroup$

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!

  • 0
    If you have words of length $L$, there are $L-1$ locations where `AA` may start, and $(L-2)^N$ ways to fill the rest; then you have $\frac{(L-3)(L-2)}{2}$ ways to put two copies of `AA`, and $(L-4)^N$ ways to fill out the rest; etc.2012-03-29

2 Answers 2

2

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

  • 0
    Sorry, I realized after 4 months that I never did tag teh correct answer :)2012-06-24
0

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--; } 
  • 0
    > The answer supplied by Gerry might be correct, but the math to solve that equation is a bit beyond me. But if are interested in a numeric solution, then the answer by Gerry -in its implicit/recursive form- is straightforward.2012-03-29