Say you had the String "RRYYYZZZZ". The number of distinct combinations you could arrange these is:
$\displaystyle \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.
Say you had the String "RRYYYZZZZ". The number of distinct combinations you could arrange these is:
$\displaystyle \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
$\displaystyle |w(e)| = \binom{9}{2 \; 3\; 4\;} = \frac{9!}{2! 3! 4!} = 1260$
and the goal of the problem is to find $\displaystyle |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, $\displaystyle 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 $\displaystyle w(e)$, the set of all 9-character strings without any restriction.
At level 2:
$\displaystyle w(RY)$ and $\displaystyle w(YR)$ are subsets of $\displaystyle w(e)$.
At level 3:
$\displaystyle w(RY.*RY)$ is a subset of $\displaystyle w(RY)$
$\displaystyle w(YR.*YR)$ is a subset of $\displaystyle w(YR)$
$\displaystyle w(RYR), w(YRY), w(RY.*YR), \text{ and } w(YR.*RY)$ are all subsets of both $\displaystyle w(RY) \text{ and } w(YR)$
At level 4:
$\displaystyle w(RYYR)$ is a subset of $\displaystyle w(RY.*YR)$
$\displaystyle w(YRRY)$ is a subset of $\displaystyle w(YR.*RY)$
$\displaystyle w(RYRY)$ is a subset of $\displaystyle w(RY.*RY), w(RYR), \text{ and } w(YRY)$
$\displaystyle w(YRYR)$ is a subset of $\displaystyle w(YR.*YR), w(RYR), \text{ and } w(YRY)$
At level 5:
$\displaystyle w(YRYRY)$ is a subset of $\displaystyle 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]