# Partitions comprised only of divisors

How many of the partitions of a natural number $n$ are comprised only of its divisors? That is, if $$p(n)=\sum_{\sum_{1}^n kj_k=n:j_k\geq 0} 1_{$j_1,j_2,...$},$$ is the ordinary partition function (i.e. the total number of partitions of $n$), then I want to know something about the counting function $$s(n)=\sum_{\sum_{d|n}dj_d=n:j_d\geq 0}1_{[j_1,...,j_d,...]}.$$

I would be happy to hear of anything that is known about this function, but I am particularly interested in (a) its generating functions, and (b) a bijection between this restricted partition and another (hopefully more intuitive to count) restricted partition. Any insights would be welcome.

I should add that google finds a number of papers that study "partitions of $n$ into divisors of $m$", e.g. Gupta, 1970s, but those methods reduce to rather vacuous statements when evaluated at $m=n$.

Thanks!

-
It's tabulated at oeis.org/A018818 but I don't see any answers there. – Gerry Myerson Dec 3 '12 at 21:48
Yes, the only thing referred to there that possibly gives a clue is the integral found when you evaluate the generating function used by Gupta at $m=n$. By Cauchy's theorem and the fact that $\sum_{d|n}phi(d)=n$, you get $$s(n)=\frac{1}{2\pi i}\int_{C}\prod_{d|n}q^{-\phi(d)}(1-q^d)^{-1}frac{dq}{q}.$$ – Kevin Smith Dec 3 '12 at 22:37
How do you edit comments to correct latex errors? If I've not got rights would somebody do so here please? – Kevin Smith Dec 3 '12 at 22:43
Comments are unfortunately not editable. You can delete it and post a corrected one (but there is no need in this case, your comment is perfectly comprehensible as it is). – Emil Jeřábek Dec 4 '12 at 11:54

$$({\tau(n)}/{2}-1)(\log n + O({\log n}/{\log \log n})) \leq \log s(n) \leq ({\tau (n)}/{2})\log n + O(\log \log n),$$ where $\tau(n)$ is the number of divisors of $n$.
Ah! Douglas, you didn't mention that it was you who set the problem! Not surprisingly their proof is marvellous, but it doesn't use anything deeper than the evaluation at $m=n$ of the coefficients of the polynomial mentioned above (though evidently this result is certainly not a trivial deployment of it). None-the-less, I remain particularly curious as yo what more is known... What were your interests in this function? How come you posed the problem? – Kevin Smith Dec 4 '12 at 17:01
I considered the function arround 1982 during a time I was doing a lot of reading on partitions and analytic number theory. My motivation was that the ordinary partition function $P(n)$ has very nice asymptotics, while in multiplicative number theory, much more irregular behavior is typical. I created the function as an interesting synthesis. I thought that the generating function would likely provide purchase for finding asymptotics. In 1989 I presented the problem at a conference, where Erdos and Odlyzko got excited about it. Monthly editors then asked me to pose it as a problem. – Douglas Bowman Dec 5 '12 at 0:27
And indeed it did provide purchase. Well, thank you for the insight, I'm very grateful. So, do you know if the upper bound is tight, or at least that $$\limsup_{n\rightarrow\infty}\frac{s(n)}{n^{\tau(n)/2}}=\infty$$? The $\liminf=1$ and this is the $\lim$ through both primes and squares of primes, but the upper bound (if tight) still suggests a lot of irregularity, specifically that $s(n)^{1/\tau(n)}=O(n^{1/2}+\epsilon)$ for every $\epsilon>0$ but not $\epsilon=0$, which is the "best-case scenario" in a lot of multiplicative number theory. – Kevin Smith Dec 5 '12 at 12:34