MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


share|cite|improve this question
It's tabulated at 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
up vote 8 down vote accepted

Bounds for this partition function were given by the editors of The American Mathematical Monthly, Paul Erdos, and Andrew Odlyzko in the March 1992 issue, p. 277, as a solution to Advance Problem number 6640. The bounds they prove are:

$$ ({\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$.

share|cite|improve this answer
Great - I'd wondered if this had cropped up. Thank you. Is an electronic copy available online do you know? I can only fond the contents page, in which the problem solutions are not listed. – Kevin Smith Dec 4 '12 at 10:18
A copy can be obtained from JSTOR: It looks like you should be able to see the article for free by creating a "My JSTOR" account. – Douglas Bowman Dec 4 '12 at 14:37
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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