Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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) = nth Taylor coefficient of 1/(1- \sum_{m ∈ 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.

share|improve this question
    
I don't understand what this is actually a plot of. –  Qiaochu Yuan Oct 21 '09 at 23:06
1  
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 –  Kevin P. Costello Oct 21 '09 at 23:11
    
Kevin is right. Sorry, I wasn't clear in my post. –  j.c. Oct 21 '09 at 23:14
add comment

2 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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 –  Kevin P. Costello Oct 21 '09 at 23:30
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.