2
$\begingroup$

A word of length $30$ needs to be formed from the letters $x, y, z$ (repeatable) with the following conditions:

  1. $y$ cannot occur more than once consecutively

  2. $z$ cannot occur more than twice consecutively.

The question is how many such words are possible.

Thanks, Kiran

  • 0
    Thats my feeling. I actually need to come with an generalized computer algorithm in the end. I am not looking for answer to the 30 length word question in particular.2011-10-08

4 Answers 4

5

Let us denote by $X_n$ the number of possible words of length $n$ ending with the letter $X$, and similarly $Y_n, Z_n$. Then the reccurence applies: $X_{n+1} = X_n + Y_n + Z_n$ $Y_{n+1} = X_n + Z_n$ $Z_{n+1} = X_n + Y_n$ $X_1 = Y_1 = Z_1 = 1$ This can be easily programmed to obtain the requested number of possibilities: X_{30} + Y_{30} + Z_{30} = X_{31} = 367'296'043'199 The recurrence can be further simplified by using $Y_n = Z_n$ (see the comment by @Gerry): $X_n = 2 X_{n-1} + X_{n-2}$ We notice that the number of sequences of the length $n$ is $X_{n+1}$. The sequence $X_n, n \ge 1$, is $\{1, 3, 7, 17, 41, 99, 239, 577, ...\}$. This are numerators of continued fraction convergents to sqrt(2). This page gives also the explicit solution: $X_n = \frac{1}{2}[(1-\sqrt{2})^n + (1+\sqrt{2})^n]$ The sequence $Y_n$ (and $Z_n$) is $\{1, 2, 5, 12, 29, 70, 169, ...\}$ which are the Pell numbers.

Since you are also interested in a program for generating the words, I posted a running C++ program to Ideone. The program represents a string $XYZ...$ by the integer in the base 3, $a = 012..$, which is stored as an array of integers $[0,1,2...]$. A new combination is generated by adding $1$ to $a$ in base 3 system and ignoring the forbidden combinations $..11..22..$.

EDIT. I included the explicit reccurence for $X_n$ based on the comment by @Gerry. He mentions also the method for finding the explicit solution.

  • 0
    @nariknahom: your question differs from projecteuler.net problem 191 !!2011-10-23
2

Consider num[L][l1][l2] = the number of words of length L starting with the two letters l1 and l2.

Your problem is to find the sum of all num[30][l1][l2] for all possible choices of l1 and l2.

There is an induction formula to express num[L][l1][l2] in terms of num[L-1][m1][m2]

  • 0
    The other solutions say, split the words up according to what they end with. Galath says, split the words up according to what they start with. It should get you to the same place.2011-10-21
1

I suggest that you define sequences for your words of length $n$ that end with x, y, one z or two zs and find recurrences for them. The computer won't mind simultaneous linear recurrences for four sequences and then summing them.

So, for example, $azz(n)=az(n-1)$ because you can only get an ending zz from a sequence ending in z.

  • 0
    A good check is also to define a sequence $b$ for words that contain yy or zzz. $b(n)=3b(n-1)+azz(n-1)+ay(n-1)$. Then the sum of all the sequences of length $n$ should be $3^n$ and you can catch some errors.2011-10-08
1

Carrying on from Jiri's 3 equations, we can eliminate $z$ to get $x_{n+1}=x_n+x_{n-1}+y_n+y_{n-1},\qquad y_{n+1}=x_n+x_{n-1}+y_{n-1}$ Subtracting gives $x_{n+1}=y_{n+1}+y_n$ Putting that into the equation for $y_{n+1}$ gives $y_{n+1}=y_n+3y_{n-1}+y_{n-2}$ Similar fiddling gets a recurrence for $x_n$ and a recurrence for $z_n$.