7
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ Confirmed for $p(n)$ even through $n=30$. Building $s$ seems pretty straightforward with just a little backtracking; you get close to $p(n)/2$ with small to medium parts and then get the remaining few by allowing large parts. The only general observations are that $1 \in s$ is required, then $2 \in s$ for $n \ge 10$ and $3 \in s$ for $n \ge 25$. By the way, this is pretty easy to check in Mathematica, e.g., the following gives 1505: Length[IntegerPartitions[27, All, {1, 2, 3, 4, 5, 6, 8, 9, 12, 22, 24}]] $\endgroup$ Aug 25, 2019 at 2:49
  • 2
    $\begingroup$ It seems to me there is an interesting generalization to ask about (or that may have already been studied; I'm far from an expert here). There are $2^n$ subsets of $\{1,2,\dots,n\}$, which is much more than $p(n)$. For a subset $S\subseteq\{1,2,\dots,n\}$, let $p_S(n)$ denote the number of partitions of $n$ whose parts are all members of $S$. What can one say about the size of the set $$ P(n)=\big\{p_S(n) : S\subseteq\{1,2,\dots,n\}\big\}? $$ Could it be the case that $|P(n)|/p(n)\to 1$? $\endgroup$ Aug 25, 2019 at 14:07
  • $\begingroup$ See an affirmative answer to a more general question Brian Hopkins asks below: mathoverflow.net/questions/339789#340021 (if it works...) $\endgroup$ Sep 7, 2019 at 20:35

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ See Ilya Bogdanov's comment above for a link to where I posted this question and he supplied a nice answer. $\endgroup$ Aug 14, 2023 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.