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?

  • $\begingroup$ 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}|$? $\endgroup$
    – Raphael
    Sep 10, 2015 at 10:05

1 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}. $$

  • $\begingroup$ @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? $\endgroup$
    – Danny
    Sep 10, 2015 at 20:28
  • $\begingroup$ @Danny Using a "positive" rather than "negative" decomposition, one reaches this formula very easily. $\endgroup$ Sep 10, 2015 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.