# Thread: Strings of letters with exclusion

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.

2. ## Re: Strings of letters with exclusion

Originally Posted by takatok
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.

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]