What I did so far, using generating function:
$[x^n] (x+x^2+\dots)(x+x^2+\dots)(1+x+x^2+\dots) = \frac{x^2}{(1-x)^3}= x^2\sum_{k=0}^\infty {3+k-1 \choose 2} x^k = \sum_{k=0}^\infty {2+k \choose 2} x^{k+2} = \sum_{k=0}^\infty {k \choose 2} x^{k}$.
I am unsure about the last step and realized that this method would only count strings without considering an order. How do we make sure that order is considered? I thought we would need to use a weight enumerator as shown here on page 2 but then I don't know what exactly I should do. Please note that I want to solve using generating function first and only then try using recursion.
If we talk about strings then the arrangements of letters in the string or sequence matters.However, if you use ordinary generating functions as you did your works, you cannot take the arrangements of letters into account, you can just find the number of sets that contain desired number of elements.
Then, we need something else here. It is exponential generating functions.It is said that $x,y$ must appear at least once,then
E.G.F for $x$: $$\frac{a^1}{1!}+\frac{a^2}{2!}+\frac{a^3}{3!}+...=(e^a-1)$$
E.G.F for $y$: $$\frac{a^1}{1!}+\frac{a^2}{2!}+\frac{a^3}{3!}+...=(e^a-1)$$
E.G.F for $z$: $$1+\frac{a^1}{1!}+\frac{a^2}{2!}+\frac{a^3}{3!}+...=e^a$$
For example, if you find the number of strings of length $n$ that obey the rule:
$$\bigg[\frac{a^n}{n!}\bigg](e^a-1)(e^a-1)e^a$$ or
$$n!\bigg[a^n\bigg](e^a-1)(e^a-1)e^a$$ or by using $$(e^a-1)(e^a-1)e^a=e^{3a}-2e^{2a}+e^a$$ It gives $$3^n-2\times2^n+1^n$$