I need to find the generating series of strings from $C = \{a, b, c\}$ without including the strings $aac$ and $baa$. Also, all $b$ substrings must have an odd length (so $bbb, cbc, aaab$ are all valid but $bbcb$ is not) and the $a$ substrings must have a minimum length of 3 (so $aaab, aaaac$ are both valid but $acaca$ isn't).
I need to find a three-variable generating series for it, $f(x, y, z) = \sum_{\delta \in C}x^{l(a)}y^{l(b)}z^{l(c)}$ where $l(a)$ is the number of $a$'s in the string, etc.
I'm not sure how to do this; I especially don't know how to incorporate the fact that there are forbidden strings. At first I was thinking I'd use a tactic similar to how one would find a generating series for compositions so that $a$ comes from the set $\{3, 4, 5, …\}$ with generating series $\frac{x^2}{1-x}$, $b$ from $\{1, 3, 5, …\}$ with generating series $\frac{x}{1-x^2}$ and $c$ from $\{1, 2, 3, …\}$ so generating series $\frac{x}{1-x}$ except this doesn't really take into account the forbidden substrings/the fact that based on how the strings are combined, the number of a given letter varies, ie $bcb$ is allowed since the length of the b blocks are odd but their total count is 2 which is even.
If anyone could help me out with how to solve/approach this problem I'd really appreciate it!
Best Answer
Here's a derivation of the one-variable generating function $f(z,z,z)$. Maybe it will help you.
Let $a_n$, $b_n$, and $c_n$ be the number of strings that start with $a$, $b$, and $c$, respectively. Then $a_0=b_0=c_0=1$, $a_1=a_2=0$, and, by conditioning on the length $k$ of the current run, we see that \begin{align} a_n &= \sum_{k=3}^n b_{n-k} &&\text{for $n \ge 3$}\\ b_n &= \sum_{\substack{k=1\\\text{$k$ odd}}}^n c_{n-k} &&\text{for $n \ge 1$}\\ c_n &= \sum_{k=1}^n (a_{n-k}+b_{n-k}-[k=n]) &&\text{for $n \ge 1$} \end{align} Let $A(z)=\sum_{n=0}^\infty a_n z^n$, $B(z)=\sum_{n=0}^\infty b_n z^n$, and $C(z)=\sum_{n=0}^\infty c_n z^n$. Then the recurrence relations imply \begin{align} A(z)-1 &=\frac{z^3}{1-z} B(z) \\ B(z)-1 &=\frac{z}{1-z^2} C(z) \\ C(z)-1 &=\frac{z}{1-z} (A(z)+B(z)-1) \end{align} Solving for $A(z)$, $B(z)$, and $C(z)$ yields \begin{align} A(z) &= \frac{1-2z-z^2+4z^3-z^4-3z^5+z^6}{1-2z-z^2+3z^3-z^4-z^5}\\ B(z) &= \frac{1-z-2z^2+3z^3-z^4}{1-2z-z^2+3z^3-z^4-z^5}\\ C(z) &= \frac{1-z-z^2+z^3+z^4-z^6}{1-2z-z^2+3z^3-z^4-z^5} \end{align} So the desired generating function (subtracting twice the $1z^0=1$ term for the empty string that is otherwise counted three times) is $$f(z,z,z)=A(z)+B(z)+C(z)-2=\frac{1-2z^2+2z^3+z^4-z^5}{1-2z-z^2+3z^3-z^4-z^5}.$$
Update: Here's the general solution. Let $f_a(x,y,z)$, $f_b(x,y,z)$, and $f_c(x,y,z)$ be the generating functions for the sequences that start with $a$, $b$, and $c$, respectively. Then \begin{align} f_a &= \frac{x^3}{1-x}(f_b+1)\\ f_b &= \frac{y}{1-y^2}(f_c+1)\\ f_c &= \frac{z}{1-z}(f_a+f_b+1) \end{align} Solving these equations yields \begin{align} f_a &= \frac{-x^3 (y^2 - y - 1) (z - 1)}{x^3 y z + x y^2 z - x y^2 - x y z - x z + x - y^2 z + y^2 + y z + z - 1}\\ f_b &= \frac{-x^3 y z + x y - y}{x^3 y z + x y^2 z - x y^2 - x y z - x z + x - y^2 z + y^2 + y z + z - 1}\\ f_c &= \frac{(x^3 - x + 1) (y^2 - y - 1) z}{x^3 y z + x y^2 z - x y^2 - x y z - x z + x - y^2 z + y^2 + y z + z - 1} \end{align} Now (including 1 for the empty string), we have $$f = f_a + f_b + f_c + 1=\frac{(x^3 - x + 1) (y^2 - y - 1)}{x^3 y z + x y^2 z - x y^2 - x y z - x z + x - y^2 z + y^2 + y z + z - 1}.$$ As a sanity check, substituting $z$ in place of $x$ and $y$ does yield the one-variable generating function obtained earlier.