Every possible number of partitions by restricting parts?

Question

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 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.

Answer 1

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.

Answer 2

There is this nice technique for generating partitions using a computer program: given a list of partitions of n, to each partition you can add a singleton class (1) to it. If that partition of n also has a smallest class (k) which is unique, you can change it to (k+1). This allows one to generate all partitions of n+1.

One can extend this. If one has a list of all partitions of n with parts (classes) of size at most k, you can do the same thing; just check that your change does not produce a class of size (k+1) in your result.

We borrow a concept from https://mathoverflow.net/a/248427, and fix an error in its expression: a sequence of integers $a_i$ is subdoubling if its first member $a_1$ is 1 and for all $i \geq 1$ we have $a_i \leq a_{i+1} \leq 2a_i$. It is a nice exercise to show that any integer from 1 up to $S_k$, the sum of the first $k$ members, is a sum of some subset (maybe more than one subset) of the first $k$ terms.

The programming technique above shows that $P(n)$ the number of partitions of $n$ is a subdoubling sequence. Also, for $k$ fixed, another subdoubling sequence is $ P(n,k)$, the number of partitions using parts of size at most $k$.

Let $n\gt 1$ be given and $m$ least with $2m \gt n$. By excluding a subset of $\{m,m+1,\cdots,n\}$, one can use the remaining numbers in a partition and realize any number from $P(n)$ to $P(n)-S_{n-m}-1 $, where I am using the notation above and assuming $a_k = P(k)$ as the subdoubling sequence. This is because the number of partitions of $n$ that have a part of size $j$ with $m \leq j \leq n$ is $P(n-j)$, and no partition of n has two parts of those sizes.

To get smaller counts, I have to omit numbers smaller than m, and then add back in enough numbers greater than m to ensure a good count. I hope to use $P(n,k)$ for this. I will stop here and save the conclusion for later.

Edit 2019.09.04:

I am proceeding cautiously, so will just report some progress.

Taking $m= \lceil (n+1)/2 \rceil$, and letting $k=m-1$, we can use the set $\{1,\cdots,k\}$ and add a few more numbers to that to get the top part of the interval $[0,P(n)]$; now I want to augment the set $\{1,\cdots,k-1\}$ with some more numbers to get an adjacent part of the interval. This means replacing the set of partitions counted by $P(n,k)$ by enough partitions so that any number in the adjacent part is realized.

Well, by splitting that set into the parts that use k, the count of the partitions that use one $ k $ is $ P(n-k,k-1)$ while the count that use two $k$s is $P(n-2k,k-1)$, so we have to "replace" all those partitions using $k$ with enough partitions not using $k$.

The latter term is at most 1, and since $P(j,k-1)$ is subdoubling in $j$ with $k-1$ fixed, we can actually go up to past $P(n-k,k-1)$ in number as the sum (for $n$ large enough, as sufficiently many small cases have already been checked by computer) of earlier terms exceed $P(n-k,k-1)$. So we can handle the case of "removing" $k=m-1$.

This argument seems to extend for large $n$ and for $k$ with $3k \gt n$. If it holds up, then the next goal is to extend it to $k$ with $4k \gt n$.

End Edit 2019.09.04. Gerhard "Parts Is Parts Is Parts" Paseman, 2019.09.04.