# 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>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?

• Have you tried partitioning the language w.r.t. $w$? For example, $w \in b\{a,b\}^{n-2}b$ is easy; can you maybe count $M_{m,n}$ restricted to $w \in a^j \{a,b\}^{n-j-k} a^k$ for each $(j,k)$ and then sum? This may be easier when counting for all $m,n$ at once, e.g. using generating functions. Can you come up with a recurrence for $|M_{m,n}|$? – Raphael Sep 10 '15 at 10:05

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}.$$
• @Yulvas Filmus Thank you. Your hint leads me to the solution: $|M_{m,n}|=(m+2)\cdot 2^{n-1}$ which not by accident also matches my observations on $M_{m,1}$ and $M_{m,2}$. Very helpful. Do you have an intuition to explain that simple formula directly? – Danny Sep 10 '15 at 20:28