Say you had the String "RRYYYZZZZ". The number of distinct combinations you could arrange these is:
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
and the goal of the problem is to find . We will also find it useful to let .* denote any sequence of zero or more characters, so, for example, 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 , the set of all 9-character strings without any restriction.
At level 2:
and are subsets of .
At level 3:
is a subset of
is a subset of
are all subsets of both
At level 4:
is a subset of
is a subset of
is a subset of
is a subset of
At level 5:
is a subset of
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]