# arranging a 30 character word with letters x, y, z

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

-
What methods do you know? –  Phira Oct 8 '11 at 10:39
I dont know how to solve this. I need to know how to approach solving this problem. I know basic permutation/combination techniques. –  nariknahom Oct 8 '11 at 10:48
And do you have reason to believe that these techniques are appropriate here? –  Phira Oct 8 '11 at 10:49
@lumbric: We usually don't add the (homework) tag without the OP's consent even if this question has the distinctive touch of a homework question. For example, it could also come from self-study, hence I removed the tag again. –  t.b. Oct 8 '11 at 10:57
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. –  nariknahom Oct 8 '11 at 10:57

## 4 Answers

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.

-
I know there are places where people write $8\cdot9$ to mean what I write as $8.9$, but I never knew there was a place where people write $6'789$ to mean what I write as $6,789$. –  Gerry Myerson Oct 21 '11 at 5:44
@Gerry, I am lucky to live in Central Europe, where a lot of daily mathematics is logical. We count and measure in the decimal system (except the time), we write the date as DD.MM.YYYY and we use ' as the thousands separator in order not to confuse it with the decimal point or decimal comma. BTW, I added some further info about the sequences and looked at your formulae (+1). –  Jiri Oct 21 '11 at 8:43
Cool. There certainly is a closed form for $x_n$. It satisfies $x_n=2x_{n-1}+x_{n-2}$, so $x_n=c_1r_1^n+c_2r_2^n$, where $r_i$ are the roots of $r^2-2r-1=0$, and $c_i$ can be figured out from $x_1=1$, $x_2=3$. –  Gerry Myerson Oct 21 '11 at 10:18
@Gerry: I completed my answer based on your observations. Thanks! –  Jiri Oct 21 '11 at 12:18
the answer is 1918080160 –  nariknahom Oct 21 '11 at 18:14

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]

-
i am new to this. what is the theory behind this? –  nariknahom Oct 21 '11 at 18:11
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. –  Gerry Myerson Oct 21 '11 at 23:19

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.

-
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. –  Ross Millikan Oct 8 '11 at 23:01

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

-