How many words are in this sets? I have problems to determine the size of the following sets in dependancy of the parameters $m, n&gt;0$:
$$M_{m,n}=\{a^iwa^{m-i}\mid 0\le i \le m,\;w\in\{a,b\}^n\}$$
It is easy to see that $|M_{m,n}|\le (m+1)\cdot 2^n$ since there are $m+1$ possibilities for $i$ and $2^n$ possibilities for $w$. If the sets would take the words $w$ from a disjoint alphabet (e.g. $w\in\{b,c\}^n$), then the number of elements would be exactly $(m+1)\cdot 2^n$. But for $w\in\{a,b\}^n$ each set $M_{m,n}$ is ambiguous in the sense that the some words could be obtained from different $i$'s and $w$'s. For example $w=a^n$ leads to the same word $a^{n+m}$ for each $i$. By the way, this example yields $|M_{m,1}|=m+2$ because there is $1$ element for $w=a $ and $m+1$ elements for $w=b$. Another ambigious example for $n=2$ is $$a^i\;ab\;a^{m-i}=a^{i+1}\;ba\;a^{m-i-1}$$ for $0\le i \le m-1$, which together with the thoughts for unary $w$'s yields $|M_{m,2}|=2m+4$.

However, for increasing $n$ it becomes more and more difficult and unfortunately I am not able to generalize my approach. What I am hoping for is that $|M_{m,n}|$ is still in $\Theta(m\cdot 2^n)$. Any help?
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}.
$$