Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Problem: count the number of distinct ways to write number X as the sum of numbers {a, b, c...} with replacement. For instance, there are 3 ways to write 11:
2+2+7
2+2+2+2+3
2+3+3+3

And if I remember correctly, isn't there a way to solve this using generating functions or polynomials of some sort?

(this question inspired by: http://www.topcoder.com/stat?c=problem_statement&pm=42&rd=2001)

share|improve this question
1  
Integer partition –  picakhu Jan 22 '11 at 20:06
1  
and based on what you seem to be doing, it is prime partition –  picakhu Jan 22 '11 at 20:07

2 Answers 2

up vote 7 down vote accepted

I believe the problem is called counting restricted partitions. (Warning: combinatorialists use the word "partition" in two different ways, and sometimes it's not completely clear from context which one is meant. One must distinguish between partitions of a number, which is the sense meant here, and partitions of a set.) With replacement, the answer is that the number $s_n$ of ways has generating function

$$\sum_n s_n x^n = (1 + x^a + x^{2a} + ...)(1 + x^b + x^{2b} + ...)(1 + x^c + x^{2c} + ...)...$$

or equivalently

$$\frac{1}{(1 - x^a)(1 - x^b)(1 - x^c)...}.$$

This is because choosing a term from each factor corresponds to choosing how many times you use each number you can use. For example, with the choices $\{ 1, 2, 5, 10, 25 \}$, this is the problem of counting the number of possible ways to make change for a certain amount of money.

The generating function can be converted into an explicit formula when the set of possibilities is finite, but it is messy in the general case and not really worth caring about. It leads to a straightforward asymptotic which I could explain if you are interested.

share|improve this answer
1  
I guess I do not understand his example if he is dealing with restricted partitions. –  picakhu Jan 22 '11 at 21:37
    
The example is a = 2, b = 3, c = 7. At least that is how I interpreted it. –  Qiaochu Yuan Jan 22 '11 at 21:49
    
@picakhu I interpreted it as a prime partition, and made the below answer. Probably not what the OP wanted though, because it is very complicated!!! –  Eric Naslund Feb 17 '11 at 3:42

If you are indeed looking at prime partitions, this is a very complicated problem. The usual counting generating series approach will unfortunately not yield too much without additional powerful analytic techniques.

Here is the abstract of R.C. Vaughn's paper "On the number of partitions into primes.":

Let $p(n)$ denote the number of ways to write a positive integer $n$ as a sum of prime numbers. Because of the irregularity in the distribution of prime numbers, it has long been believed that it is not possible to obtain an asymptotic formula for $p(n)$. (Of course, this depends on what one means by an asymptotic formula.) In this paper, the author obtains a formula for $p(n)$ in the form $$ p(n)=M(n)(1+O(n^{-1/5})) \quad (n\to\infty), $$ where $M(n)$ is a smooth function whose definition involves the generating function of $p(n)$. Moreover, using the same analytic method, the author obtains the following remarkable result: $$ p(n+1)-p(n)\sim\frac{\pi p(n)}{\sqrt{3n\log n}} $$

Reading this paper will definitely give some insights. Also, to see the sequence $p(n)$ you can visit this OEIS page.

Hope that helps,

share|improve this answer
    
It is not clear to me that you are discussing prime partitions, since for $11$ there are $6$ possible partitions: $2+2+7$, $\text{ }$ $2+2+2+2+3$, $\text{ }$ $2+3+3+3$, $\text{ }$ $5+2+2+2$, $\text{ }$ $5+3+3$, $\text{ }$ $11$. –  Eric Naslund Jan 22 '11 at 21:13

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.