How many words are in this sets?
Count instead
$$
(a+b)^{n+m} - M_{m,n} = \sum_{i+j &lt; m} a^i b (a+b)^{n+m-2-i-j} b a^j.
$$
This leads to
$$
\begin{align*}
|M_{m,n}| &amp;= 2^{n+m} - \sum_{i+j&lt;m} 2^{n+m-2-i-j} \\
&amp;= 2^{n+m} - \sum_{k=0}^{m-1} (k+1) 2^{n+m-2-k} \\ &amp;=
2^{n+m} - 2^{n+m-2} (4-2^{-(m-2)}-m2^{-(m-1)}) \\ &amp;=
2^{n+m} (1 - 1 + 2^{-m} + m2^{-m-1}) \\ &amp;=
(m+2) 2^{n-1}.
\end{align*}
$$

A more direct method follows the decomposition
$$
M_{m,n} = \sum_{i=0}^{m-1} a^ib(a+b)^{n-1}a^{m-i} + a^m(a+b)^n.
$$
This directly gives
$$
|M_{m,n}| = m 2^{n-1} + 2^n = (m+2) 2^{n-1}.
$$