How many words are in this sets?

Question

I have problems to determine the size of the following sets in dependancy of the parameters $m, n>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?

Answer 1

Count instead $$ (a+b)^{n+m} - M_{m,n} = \sum_{i+j < m} a^i b (a+b)^{n+m-2-i-j} b a^j. $$ This leads to $$ \begin{align*} |M_{m,n}| &= 2^{n+m} - \sum_{i+j<m} 2^{n+m-2-i-j} \\ &= 2^{n+m} - \sum_{k=0}^{m-1} (k+1) 2^{n+m-2-k} \\ &= 2^{n+m} - 2^{n+m-2} (4-2^{-(m-2)}-m2^{-(m-1)}) \\ &= 2^{n+m} (1 - 1 + 2^{-m} + m2^{-m-1}) \\ &= (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}. $$