Partitions restricted to only certain summands

Question

Here $n$ is a positive integer and $p(n)$ is the number of unrestricted partitions.

Can one always find a subset $s$, of $\{1,2,\ldots,n\}$ such that the number of partitions of $n$ with parts from $s$ is $p(n)/2$ if $p(n)$ is even and is $[p(n)+1]/2$ or $[p(n)-1]/2$ if $n$ is odd?

For example: if $n=7$ we may choose $s$ to be $\{1,3,4,5,7\}$. The partitions of 7 which are to be counted are $$ \begin{split} &7\\ &5+1+1\\ &4+3\\ &3+3+1\\ &4+1+1+1\\ &3+1+1+1+1\\ &1+1+1+1+1+1+1\\ \end{split} $$ and $[p(n)-1]/2= (15-1)/2=7$ so we can do what was asked of us.

Answer 1

Not a proven answer, but evidence that the problem can always be solved fairly easily and a suspicion that a much stronger result is true.

Using a greedy approach, I was able to construct the desired set $S$ for each $n$ with $p(n)$ even up to $n=50$ (I focused on the even case since they have a single target value). Write $p_S(n)$ for the number of partitions of $n$ with parts from $S$.

1. Given $n \ge 2$, find the smallest $k$ so that $p_{\{1,\ldots, k\}}(n) > p(n)/2$.
2. Consider $S=\{1,\ldots,k-1,k+1\}$, $\{1,\ldots,k-1,k+2\}$, etc., to the first occurrence of $P_S(n) \le p(n)/2$. Let $\ell$ be the new part and set $S=\{1,\ldots,k-1,\ell\}$.
3. If $p_S(n) < p(n)/2$, then repeat Step 2 considering $S = \{1,\ldots,k-1,\ell,\ell+1\}$, $\{1,\ldots,k-1,\ell,\ell+2\}$, etc.

For example, this procedure for $n = 50$ leads to $S=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 20, 32, 46\}$.

It's not apparent that the algorithm gives an $S$ for which $p_S(n)$ lands exactly on $p(n)/2$. The intuition for why it works is that allowing large parts (close to $n$) increases the partition count by a small number, allowing fine adjustments to $p_S(n)$. In the $n=50$ example, $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 20, 32, 47\}$ gives 102,111 rather than the desired 102,113. Then $S=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 20, 32, 47, 48\}$ gives a different set with $p_S(n) = p(50)/2$.

The fact that no backtracking was required through $n=50$ suggests that there are several choices for $S$. Further, there does not seem to be anything special about the values $p(n)/2$, $(p(n) \pm 1)/2$. I verified for $n=19$ that for every $k$ satisfying $1 \le k \le p(19) = 490$, there is an $S$ for which $p_S(n) = k$.

Could it be that, given $n$ and any $k$ with $1 \le k \le p(n)$, there is always an $S \subseteq \{1, \ldots, n\}$ such that $p_S(n) = k$?

Certainly the number of subsets grows much faster than $p(n)$...