Let $n$ be a natural number. Let $dc(n)$ be the number of compositions of $n$ where the summands are required to be in the set of divisors of $n$. Standard lore in analytic combinatorics yields the following formula for $dc(n)$:

$$dc(n) = n\text{th Taylor coefficient of }\frac{1}{1- \sum_{m\in\text{divisors of n}} z^m}.$$

But what are the asymptotics of $dc(n)$? Here's a plot that I made (the y-axis is $dc(n)$ on a log scale and the x-axis is $n$):

Compositions from divisors

I would like to understand the "fanning", which presumably has something to do with whether numbers have lots of small divisors or not, and I would also like to understand why these fans seem to be so close to exponentials. The solid fit line at the top is $2^n$, which is the number of unrestricted compositions.

If that's too much to ask for, I guess I'd like to know how one might use known facts about the number of divisors, etc. to say something about this, as this rather artificial construction ought to be governed by some more fundamental number theoretic functions.

  • $\begingroup$ I don't understand what this is actually a plot of. $\endgroup$ – Qiaochu Yuan Oct 21 '09 at 23:06
  • 2
    $\begingroup$ As i understand it, the x axis corresponds to n and the y axis corresponds to the number of ways of writing n as an ordered sum a_1+...+a_k, where each a_i is a divisor of n. So for example the point (4,6) is plotted, corresponding to the 6 compositions {1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 4} of 4 $\endgroup$ – Kevin P. Costello Oct 21 '09 at 23:11
  • $\begingroup$ Kevin is right. Sorry, I wasn't clear in my post. $\endgroup$ – j.c. Oct 21 '09 at 23:14

(Edited because the n/2 in the exponent in my original sketch was wrong).

Here's what might correspond to a (very) sketchy explanation as to those fans:

What does a typical (unrestricted) composition of an integer look like? Since there are 2^{n-k} compositions of n beginning with k, the expectation of the first element of the composition is actually around 2, and more generally the probability the first number is k decays exponentially with k.

In other words, a toy model for such a composition would be to successively and independently choose integers a_i such that the probability each a_i is equal to k is 2^{-k}, and stop when we reach n. This is problematic in some ways (especially when our sum gets close to n), but this should only affect the last few terms. We fail if we encounter an integer that is not a divisor of n.

By the law of large numbers we need to succeed about n/e_n times, where e_n is the expected value of a_i once we condition on the composition consisting only of divisors of n. Each integer has the same fixed probability c_n of being a divisor (here c_n depends mainly on the small divisors of n, and my intuition is that e_n would be the same way). Making a bunch of unsubstantiated independence assumptions, we would expect the probability a random composition has only divisors to be c_n^{n/e_n}. The fans then correspond to n which share the same small divisors and have approximately equal c_n and e_n.

  • $\begingroup$ As a side note, there's a wealth of people who HAVE looked at this sort of thing (what does a typical composition look like) rigorously -- you can get a tip of the iceberg by searching for "random composition"+integer $\endgroup$ – Kevin P. Costello Oct 21 '09 at 23:30

The number of compositions of n with all parts equal to 1 or 2, for example, is the (n+1)st Fibonacci number, which grows like φn where φ = (1+√5)/2.

The number of compositions of 2p for p a prime, where all parts are equal to 1, 2, p, or 2p, isn't all that much bigger. In particular I believe it has the same exponential growth rate. I suspect this is one of the lines you see.

Replacing 2 with any integer, you can do the same sort of thing; this is what causes your points to fall, for the most part, along straight lines.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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