# Thread: number of strings not containing xyz

1. ## 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.

2. ## Re: number of strings not containing xyz

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?

3. ## Re: number of strings not containing xyz

sorry, i've edited the question now.

4. ## Re: number of strings not containing xyz

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?

5. ## Re: number of strings not containing xyz

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