# Every possible number of partitions by restricting parts?

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.

• Comment to cover most small $k$ up to $\frac{3n}4$ or so: the subset $\{1,n-k+2,n-k+3,\dots,n\}$ yields $k$ partitions when $k<\frac n2-2$; the subset $\{1,2,n-t\}$ yields $\lfloor\frac n2\rfloor+\lfloor\frac t2\rfloor+2$ partitions when $t<\frac n2$. Sep 4 '19 at 2:07
• One can also look at bootstrapping by considering m approximately n/k, and building partitions using m, m+1,m+2, and so on. Gerhard "Can Get Almost Exponentially Many" Paseman, 2019.09.04. Sep 4 '19 at 9:49
• mathoverflow.net/a/248427 has the concept of subdoubling. I think I can use this to solve the problem. Gerhard "Or Cut It In Half" Paseman, 2019.09.04. Sep 4 '19 at 12:35
• @GregMartin Nice, thanks. There are also $p_S(n)$ formulas for $S=\{1,\ldots, d\}$ for small $d$ that could be similarly modified, although they get tedious fast. (I think Andrews & Eriksson's book works out $d=4$ with the euphemism "a little algebra reveals"). Sep 5 '19 at 2:53

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

• Thanks, working through this. So you're starting from $S=[n]$, right? Sep 7 '19 at 2:36
• Yes, and then going through the nimbers in increasing order. Sep 7 '19 at 6:30
• Ok, I agree that this works. There's one step I'd like to understand better. In the (*) proof, the "otherwise" case is when $m$ is not removed, so it must be that $p_{S_m} (n) < k$, i.e., $p_{S_m} (n) \le k - 1$. And $S_m = S_{m-1}$. Certainly removing $m$ cannot increase the number of partitions, but why move to $p_{S_{m-1}\setminus \{m\}}$? Sep 10 '19 at 0:43
• Sorry, I do not understand the question. I clarified a bit how $S_m$ are defined; does it help? Sep 10 '19 at 13:03
• (If the question is why do we do what we are doing', then the answer is: if $(**)$ were not corect, then for some value of $k$ the algorithm would fail; so this is mostly what we need to check, in order to decide validity of the algorithm.) Sep 10 '19 at 13:05

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.

• Great. I think I understand about getting the range of partition counts in your "Let \$n>1" paragraph. With Greg's and my comments, it looks like things can be worked out for small counts---it's all the stuff in the middle. Look forward to the conclusion you foreshadow! By the way, your subdoubling condition makes me think of lecture hall partitions. Sep 5 '19 at 3:10
• Soon after I post, I find it does not work this way for k smaller than m-1. We need to use the numbers from the smaller half judiciously. I will post an update when I get a sensible result. Gerhard "Getting The Sense Of It" Paseman, 2019.09.05. Sep 5 '19 at 13:53