Number of partitions of $n$ with different product

Question

Let $S_n$ denote the set of partions of $n$ such that every part is greater than 1. Partitions $(x_1,\ldots,x_k), (y_1,\ldots,y_l) \in S_n$ are said to have almost equal product if $$\prod_{i=1}^k (x_i+1) = \prod_{i=1}^l (y_i+1)$$.

For example if $n = 14$ the partitions (3,3,8) and (2,5,7) are almost equal since (3+1)(3+1)(8+1) = (2+1)(5+1)(7+1).

Now if we denote by $S'_n$ the largest subset of $S_n$ not containing almost equal partitons,then I would like to find the asymptotic value of $|S'_n|$. I believe $|S'_n|$ is at least subexponential in $n$ but do not know how to prove this. Is there any way to perhaps find a bound on the number of pairs of almost equal partitions and take it from there?

Answer 1

I don't know what you mean by "at least subexponential." A subexponential upper bound is trivial because the number of partitions of $n$ with no restrictions grows subexponentially.

A little work gives a superpolynomial lower bound. Choose an arbitrary subset $\{p_1,...p_k\}$ of the primes between $5$ and $f(n)$ for some function $f$ to be determined later. There are $2^{\pi(f(n))}$ such subsets, and we will create a partition of $n$, $(2,...,2,3,...,3,p_1-1,p_2-1,...p_k-1)$ such that the primes dividing the product $\prod (x_i+1)$ are $\{2,3,p_1,...p_k\}$ hence the products for partitions constructed from different subsets are distinct.

For an easy lower bound, take $f(n)=\sqrt n$. The sum of the primes up to $\sqrt n$ is smaller than $n$ by enough to create a partition of $n$ by padding with $2,...,2,3,...,3$. The prime number theorem says $\pi(\sqrt n) \sim \frac{\sqrt n}{\log \sqrt n}$ so there are at least $\exp(C \frac {\sqrt n}{\log n})$ partitions of $n$ with parts greater than $1$ and different (augmented) products. I expect that you can get rid of the $\log n$ in the denominator or at least replace it with $\log\log n$ by using a better $f(n)$.