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!

$\endgroup$
5
  • $\begingroup$ I suspect you'll end up having to do inclusion-exclusion. This is essentially the same as this problem $\endgroup$ – Arturo Magidin Mar 29 '12 at 5:14
  • $\begingroup$ Close, but not quite the same. I could do inclusion/exclusion if the set was defined. but here it's an arbitrary length alphabet with arbitrary length words $\endgroup$ – Lenny Markus Mar 29 '12 at 6:20
  • $\begingroup$ You can do inclusion-exclusion with $L$ and $N$ indicated; it's not "arbitrary length words", but rather, "unspecified length words". $\endgroup$ – Arturo Magidin Mar 29 '12 at 14:24
  • $\begingroup$ Can you show me a simple example of this? $\endgroup$ – Lenny Markus Mar 29 '12 at 15:33
  • $\begingroup$ 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. $\endgroup$ – Arturo Magidin Mar 29 '12 at 15:39
2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ I've never heard of the concept.I guess I have to investigate. What you have kinda looks like an inductive proof. $\endgroup$ – Lenny Markus Mar 29 '12 at 6:11
  • $\begingroup$ Gerry, First of all thanks for taking the time to explain this. I understand the last part, where you substitute a couple of values in order to solve A & B. The part that lost me is where you move from the quadratic equation, to the Xl based equation. I understand that r and s are the solutions to the quadratic equation, but I fail to see where xl= Ar^l + Bs^l came from. $\endgroup$ – Lenny Markus Mar 30 '12 at 1:57
  • $\begingroup$ It's a little tricky to see where it came from, but easier to see why it works. Use $x_L=Ar^L+Bs^L$ to write formulas for $x_{L+1}$ and $x_{L-1}$ and stick them in the recurrence relation, do a little algebra, and you will see the quadratic equation materialize out of nowhere. Having seen this bit of magic before, I know how to go from the recurrence to the quadratic to the solution of the recurrence. If you're still puzzled, any intro text on discrete math should have a chapter on recurrences which will explain it in detail. $\endgroup$ – Gerry Myerson Mar 30 '12 at 2:57
  • $\begingroup$ I understand why it works, but yeah, still having a little trouble wrapping my head around where xL=ArL+BsL came from. Any particular book you would recommend on the subject? $\endgroup$ – Lenny Markus Mar 30 '12 at 3:52
  • $\begingroup$ As I said, pretty nearly any intro discrete math textbook should do you. Just make sure it has a chapter on recurrence relations. $\endgroup$ – Gerry Myerson Mar 30 '12 at 4:45
0
$\begingroup$

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--;
}
$\endgroup$
1
  • $\begingroup$ > 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. $\endgroup$ – leonbloy Mar 29 '12 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.