Thread: number of strings not containing xyz

hi, what is the number of strings made of only x, y and z and of length n which do not contain the pattern 'xyz' anywhere in them ?
for the pattern 123 we can use the catalan sequence but what about 'xyz'?
e.g for n = 2 , the number of such strings is 9
thanks.

Originally Posted by pranay

hi, what is the number of strings which do not contain the pattern xyz anywhere in them ?
for the pattern 123 we can use the catalan sequence but what about xyz?

There is no way to answer as posted.
Strings of what?
How long are the strings?
Please complete the question!

sorry, i've edited the question now.

Originally Posted by pranay

sorry, i've edited the question now.

Your edit did absolutely nothing to clear things up.
Are you using the alphabet, a to z?
If so how long are the strings?
Can letters be repeated?

Originally Posted by Plato

Are you using the alphabet, a to z?

no, the string is made of only the alphabets X,Y and Z

.
If so how long are the strings?

The string can be of any length (n<=30)

Can letters be repeated?

Yes but the string must not contain the pattern 'XYZ'
a valid such string of length 5 is XXYYZ while an invalid one is XYZZZ.

For the case of strings containing only digits 1,2 and 3 ,the number of them of lenght n which do not contain the pattern '123' can be got by the nth Catalan number, so is there any relationship here in case of strings having X,Y and Z and not containing 'XYZ' pattern?
Thanks