Write $p(n)$ for the number of integer partitions of $n$. For $S \subseteq \{1, \ldots, n\}$, let $p\_S(n)$ be the number of partitions of $n$ with all parts in $S$. So $p(n) = p\_{\{1,\ldots,n\}}(n)$. 



> 
> Conjecture: Given positive integers $n$ and $k$ with $0 \le k \le p(n)$, there is an $S \subseteq \{1, \ldots, n\}$ such that $p\_S(n)=k$.
> 
> 
> 


I have verified this through $n=20$. Some very loose intuition supporting the conjecture is that the number of subsets grows much faster than $p(n)$. 


This conjecture is inspired by David Newman's [question](https://mathoverflow.net/questions/339124) where he wonders about $S$ with $p\_S(n)=p(n)/2$ or $(p(n)\pm1)/2$. My non-answer there suggests that a greedy algorithm is enough to find the $S$ he wants, verified for even $n$ up to 50.



Every possible number of partitions by restricting parts?
The conjecture seems to hold.


For brevity, denote $[k,n]=\{k,k+1,\dots,n\}$ and $[n]=[1,n]$. Start with $S = [n]$.


**Algorithm:** Given $0\leq k\leq p(n)$, consider the numbers $1,2,\dots,n$ one by one, removing the number if the remaining set $S$ satisfies $p\_S(n)\geq k$. After all $n$ numbers are considered, we are done.


Let $S\_m$ be the set obtained after considering the numbers up to $m$. Hence, the algorithm reads as follows: $S\_m=S\_{m-1}\setminus\{m\}$ if $p\_{S\_{m-1}\setminus\{m\}}(n)\geq k$, and $S\_m=S\_{m-1}$ otherwise.


We claim that at each step, the inequality
$$
 p\_{S\_m\cap[m]}(n)\leq k
 \qquad(\*)
$$
holds. If $(\*)$ is proved, we will get $k\leq p\_{S\_n}(n)\leq k$, as required.


We prove $(\*)$ by induction on $m$. Clearly, it holds for $m=0$. Assume now that $p\_{S\_{m-1}\cap[m-1]}(n)\leq k$. If $S\_m=S\_{m-1}\setminus\{m\}$, then $S\_{m-1}\cap[m-1]=S\_m\cap[m]$, and $(\*)$ holds. Otherwise, $S\_m=S\_{m-1}$, which means that $p\_{S\_{m-1}\setminus\{m\}}(n)\leq k-1$. So, in order to finish this case, it suffices to show that
$$
 p\_{S\cap[m]}(n)\leq p\_{S\setminus\{m\}}(n)+1 \qquad(\*\*)
$$
for every $S\supseteq[m,n]$ (and apply it to $S=S\_{m-1}$). If $m=n$, the inequality is obvious. Otherwise, we will show even the version without `$+1$'.


We present an ``injective'' proof, after taking the complements. Namely, to each partition with parts in $S$, at least one of which equals $m$, we assign a partition with parts in $S$, at least one of which exceeds $m$, so that this correspondence is injective. This will prove 
$$
 p\_S(n)-p\_{S\setminus\{m\}}(n)\leq p\_S(n)-p\_{S\cap[m]}(n),
$$
which yields $(\*\*)$.


The partitions containing both $m$ and $>m$ correspond to themselves. Now take any partition with maximal element $m$. If it contains a unique copy of $m$, let $a(<m)$ be the minimal element of the partition; replace now $m$ and $a$ by $m+a$. Finally, if the partition contains exactly $d>1$ copies of $m$, replace them by $dm$. Clearly, this correspondence is injective, as required.


