Results 1 to 2 of 2

Math Help - Strings of letters with exclusion

  1. #1
    Junior Member
    Joined
    Nov 2011
    Posts
    53
    Thanks
    1

    Strings of letters with exclusion

    Say you had the String "RRYYYZZZZ". The number of distinct combinations you could arrange these is:

    \frac{9!}{2!3!4!}

    What if we didn't allow any Y to touch an R. I"m at a loss at how to go about excluding those.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: Strings of letters with exclusion

    Quote Originally Posted by takatok View Post
    Say you had the String "RRYYYZZZZ". The number of distinct combinations you could arrange these is:

    \frac{9!}{2!3!4!}

    What if we didn't allow any Y to touch an R. I"m at a loss at how to go about excluding those.
    Hi takatok,

    Here is a sketch of a solution via inclusion-exclusion.

    By way of notation, let's say that w(s) is the set of 9-character words that can be formed that include the substring s, so w(RY), for example, is the set of 9-character strings from the allowed multiset which contain the substring RY. Vertical bars denote cardinality. So, for example, if we let e denote the empty string, then we can write
    |w(e)| = \binom{9}{2 \; 3\; 4\;} = \frac{9!}{2! 3! 4!} = 1260
    and the goal of the problem is to find |w(e) \cap (w(RY) \cup w(YR))^c|. We will also find it useful to let .* denote any sequence of zero or more characters, so, for example, w(RY.*YR) is the set of 9-character words that include RY followed by YR, with zero or more characters between them.

    In order to apply inclusion-exclusion we must determine the lattice of subsets we are interested in. I would sketch the lattice for you if I could, but I'm not good at graphics and the lattice is a real mess anyway. So here is how it goes from the top down. If I were you I would attempt a sketch from this despite its being a mess.

    At the top (let's say this is level 1), we have w(e), the set of all 9-character strings without any restriction.

    At level 2:
    w(RY) and w(YR) are subsets of w(e).

    At level 3:
    w(RY.*RY) is a subset of w(RY)
    w(YR.*YR) is a subset of w(YR)
    w(RYR), w(YRY), w(RY.*YR), \text{ and } w(YR.*RY) are all subsets of both w(RY) \text{ and } w(YR)

    At level 4:
    w(RYYR) is a subset of w(RY.*YR)
    w(YRRY) is a subset of w(YR.*RY)
    w(RYRY) is a subset of w(RY.*RY), w(RYR), \text{ and } w(YRY)
    w(YRYR) is a subset of w(YR.*YR), w(RYR), \text{ and } w(YRY)

    At level 5:
    w(YRYRY) is a subset of w(RYRY) \text{ and } w(YRYR)

    This should be enough for you to apply inclusion-exclusion. I think the sizes of all the subsets listed above a pretty easy to compute, at least by comparison with the complexity of the lattice of subsets.

    The final answer is 200.

    [edit]By inclusion-exclusion, the final answer is S(1) - S(2) + S(3) - S(4) + S(5), where S(i) is the sum of the sizes of the sets at level i. But you should already know that it you are attempting this problem anyway.[/edit]
    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, 08:06 AM
  2. How many bit strings of length 27 are there...?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 21st 2010, 10:39 AM
  3. Matlab - Need help on strings
    Posted in the Math Software Forum
    Replies: 1
    Last Post: March 28th 2010, 10:45 AM
  4. Bit strings
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 10th 2009, 11:07 AM
  5. strings
    Posted in the Statistics Forum
    Replies: 10
    Last Post: January 17th 2009, 12:35 PM

Search Tags


/mathhelpforum @mathhelpforum