# 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, What's the name of this problem?

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
What's the name of this problem?
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

ululatonh
With replacement, the answer is that the number ${s}_{n}$ of ways has generating function
$\sum _{n}{s}_{n}{x}^{n}=\left(1+{x}^{a}+{x}^{2a}+...\right)\left(1+{x}^{b}+{x}^{2b}+...\right)\left(1+{x}^{c}+{x}^{2c}+...\right)...$
or equivalently
$\frac{1}{\left(1-{x}^{a}\right)\left(1-{x}^{b}\right)\left(1-{x}^{c}\right)...}.$
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 $\left\{1,2,5,10,25\right\}$, 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.
###### Did you like this example?
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.
Let $p\left(n\right)$ 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\left(n\right)$. (Of course, this depends on what one means by an asymptotic formula.) In this paper, the author obtains a formula for $p\left(n\right)$ in the form
$p\left(n\right)=M\left(n\right)\left(1+O\left({n}^{-1/5}\right)\right)\phantom{\rule{1em}{0ex}}\left(n\to \mathrm{\infty }\right),$
where $M\left(n\right)$ is a smooth function whose definition involves the generating function of $p\left(n\right)$. Moreover, using the same analytic method, the author obtains the following remarkable result:
$p\left(n+1\right)-p\left(n\right)\sim \frac{\pi p\left(n\right)}{\sqrt{3n\mathrm{log}n}}$
###### Did you like this example?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee