5
$\begingroup$

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)

  • 1
    and based on what you seem to be doing, it is prime partition2011-01-22

2 Answers 2

7

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.

  • 0
    @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!!!2011-02-17
1

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,

  • 0
    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$.2011-01-22