A partition problem I want to enumerate the partitions of $\{1,2,\ldots,n\}$ into disjoint sets $A$ and $B$ such that no subset of $B$ has a sum that is a member of $A$. 
For example, when $n=3$ there are $7$ such partitions: 
\begin{align*}
A&=\emptyset,B=\{1,2,3\}\\
A&=\{1\},B=\{2,3\},\\
A&=\{2\},B=\{1,3\},\\
A&=\{1,2\},B=\{3\},\\
A&=\{1,3\},B=\{2\},\\
A&=\{2,3\},B=\{1\},\\
A&=\{1,2,3\},B=\emptyset,
\end{align*}
Note that $A=\{3\},B=\{1,2\}$ is not a valid since there is a subset of $B$ whose sum is a member of $A$, namely $B$ itself. That is, $1+2=3\in A$.  
I can do this numerically (by building the subsets recursively) but is there a way of theoretically determining this number? 
 A: Since no one has answered yet...
An upper bound is obviously $2^n$.
A lower bound is $2^{\lfloor n/2\rfloor+1}$ (since there are these many subsets of $C=\{\lceil n/2 \rceil,...,n\}$, and any pair of distinct integers equal to or greater than $\lceil n/2 \rceil$ adds up to more than $n$, so any of these subsets qualifies for $A$).
I believe, in fact, that one can prove an upper bound of $2^{n/2}poly(n)$. The very informal reasoning is the following. 
Consider all subsets of $C$ of cardinality $m$. In how many ways can I "extend" any generic one of them $S$ (solely) with elements from $\{1,...,\lceil n/2 \rceil-1\}$ without violating the no-sum-in-the-other-partition rule (I'll call these legal extensions)? Consider a "Poissonized" choice of $S$, where each element of $C$ is inserted in $S$ with probability $\gamma=m/|C|$ (so I don't get exactly cardinality $m$, but close enough, and I think everything can be formalized properly) and now consider an integer $p$ in $\{1,...,\lceil n/2 \rceil-1\}$. How likely is it that $p$ can be added? Let's think now of going through the numbers $\lceil n/2 \rceil, ..., n-p$; if for any such number $q$ one but not both of $q$ and $p+q$ are in $S$ then I can't add $p$ to $S$. What's the probability of being able to add $p$? Let's focus on $m<\lceil|C|/2\rceil$ i.e. $\gamma\lesssim \frac{1}{2}$, since it's easy to see that for $\gamma\gtrsim\frac{1}{2}$ the situation is symmetrical (also in terms of number of subsets with that cardinality). For each $q$, the probability of $p$ "surviving" $q$ is $\gamma(1-\gamma)$, so $p$ has on average a probability bounded away from $0$ of surviving the whole process if it's roughly between $n/2$ and $n/2-\frac{1}{\gamma}$, a probability a constant factor smaller on average if it's roughly between $n/2-\frac{1}{\gamma}$ and $n/2-\frac{2}{\gamma}$ and so on. All told, we can then expect to add $O(\frac{1}{\gamma})$ different numbers to $S$, and so extend it in $2^{O(\frac{1}{\gamma})}=2^{O(n/m)}$ ways (note that this is an upper bound). 
Now, one could actually make an almost identical argument on the ways to extend subsets of  $\{1, ...,\lceil n/2 \rceil-1\}$ with elements solely of $C$, showing that if one starts with cardinality $m$ one can extend a subset "legally" in  $2^{O(\frac{1}{\gamma})}=2^{O(n/(m))}$ ways (again, an upper bound). Then, every subset of $\{1,...,n\}$ satisfies at least one of the following three properties:


*

*It has at most $\frac{n}{2\lg(n)}$ elements.

*It has at least half its elements in $C$.

*It has at least half its elements outside $C$.


The subsets with property $0$ are at most $n^{\frac{n}{2\lg(n)}}=2^{n/2}$, so they won't budge the $2^{n/2}poly(n)$.
The subsets of with property $1$ but without property $0$ are subsets of $C$ that were be extended in at most $2^{O(n/m)}$ ways with $m\geq \frac{n}{2\lg(n)}$ i.e. in at most $2^{O(\lg(n))}=poly(n)$ ways; we know that there are $O(2^{n/2})$ subsets of $C$, so the subsets with property $1$ but not property $0$ are at most $2^{n/2}poly(n)$, and the same can be said of those with property $2$ but not property $0$.
