Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

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.

share|improve this answer
1  
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
1  
@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
show 3 more comments

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]

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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