number of strings not containing xyz

• Aug 16th 2011, 07:38 AM
pranay
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.
• Aug 16th 2011, 07:45 AM
Plato
Re: number of strings not containing xyz
Quote:

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?
• Aug 16th 2011, 08:53 AM
pranay
Re: number of strings not containing xyz
sorry, i've edited the question now.
• Aug 16th 2011, 09:18 AM
Plato
Re: number of strings not containing xyz
Quote:

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?
• Aug 16th 2011, 05:00 PM
pranay
Re: number of strings not containing xyz
Quote:

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
Quote:

.
If so how long are the strings?
The string can be of any length (n<=30)
Quote:

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