Results 1 to 5 of 5

Math Help - number of strings not containing xyz

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    95

    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.
    Last edited by pranay; August 16th 2011 at 08:50 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,923
    Thanks
    1762
    Awards
    1

    Re: number of strings not containing xyz

    Quote Originally Posted by pranay View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2010
    Posts
    95

    Re: number of strings not containing xyz

    sorry, i've edited the question now.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,923
    Thanks
    1762
    Awards
    1

    Re: number of strings not containing xyz

    Quote Originally Posted by pranay View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2010
    Posts
    95

    Re: number of strings not containing xyz

    Quote Originally Posted by Plato View Post
    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
    Last edited by pranay; August 16th 2011 at 06:16 PM. Reason: added more data
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. How many eight-bit strings contain exactly three 0's
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 4th 2010, 09:06 AM
  2. Number of binary Strings Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 14th 2010, 08:09 AM
  3. Matlab - Need help on strings
    Posted in the Math Software Forum
    Replies: 1
    Last Post: March 28th 2010, 11:45 AM
  4. Bit strings
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2009, 12:07 PM
  5. strings
    Posted in the Statistics Forum
    Replies: 10
    Last Post: January 17th 2009, 01:35 PM

Search Tags


/mathhelpforum @mathhelpforum