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]