Count expressions with 1s and 2s Given at most X number of 1s and at most Y number of 2s. How many different evaluation results are possible when they are formed in an expression containing only addition + sign and multiplication * sign are allowed?
Note that, multiplication takes precedence over addition.
For example, if A=2 and B=2, then we have the following expressions:
1, 1*1 = 1
2, 1*2, 1*1*2, 1+1 = 2
1+2, 1+1*2 = 3
2+2, 2*2, 1+1+2, 1*2*2, 1*1*2*2, 1*2+1*2, 1*1*2+2, 1*2+2 = 4
1+2+2, 1+1*2+2 = 5
1+1+2+2 = 6

So there are 6 unique results that can be formed if A = 2 and B = 2.
So here answer would be 6.

Source
This question is from  March 2014 Hacker Rank contest which has ended by now.
 A: These are some thoughts toward a solution.
As user45878 and I noted in comments, the largest number you can get in the prescribed fashion using at most $m$ $1$'s and $n$ $2$'s is $2^n+m$.  Moreover, you can clearly get all numbers from $2^n$ to $2^n+m$.  So the problem boils down to asking how many numbers less than $2^n$ can you form?
Since $1\times1=1$ and $1\times2=2$, we may as well limit ourselves to considering expressions of the form
$$2\circ2\circ\cdots\circ2+1+1+\cdots+1$$
where the expression contains up to $n$ $2$'s and $m$ $1$'s, and each "$\circ$" is either a "$+$" or a "$\times$."  There are additional simplifications as well.  The $2\circ2\circ\cdots\circ2$ part can be rewritten as
$$2^a+2^b+\cdots+2^z$$
with $a\gt b\gt\cdots\gt z\gt0$ and $a+b+\cdots+z\le n$.  The role of the $1$'s is to try to fill in the gaps between numbers that can be written with a limited number of powers of $2$.
An example might help.  Let's consider $n=4$.  The distinct possibilities for $2\circ\cdots\circ2$ are $2$, $2^2$, $2^2+2$, $2^3$, $2^3+2$, and $2^4$, that is,
$$2,4,6,8,10,16$$
We see that the numbers $1,3,5,7,9,11,12,13,14$, and $15$ are missing.  If $m=1$, we pick up $1,3,5,7,9$, and $11$.  With each additional $1$, we pick up one more number until we reach $m=5$.  One might express this as follows:
$$M_4(0)=10,\quad M_4(1)=4,\quad M_4(2)=3,\quad M_4(3)=2,\quad M_4(4)=1,\quad M_4(5)=0$$
where $M_n(m)$ denotes the numbers up to $2^n$ (or, if you like, $2^n+m$) that are "missing" from the prescribed expressions with at most $m$ $1$'s and $n$ $2$'s.  One can obviously obtain the number of "present" numbers as
$$P(m,n)=2^n+m-M_n(m)$$
If I have any additional (or multiplicative) thoughts, I'll post them.
