0

In how many ways can I sum elements $a,b,c,d,...$ such that they add up to $n$?

For example, $1,2,3$ can be summed to $4$ in $4$ ways because:

$$4 = 1+1+1+1 = 2+2 = 1+3 = 2+1+1$$

If two ways use the same values but in other order (e.g. $1+2+1$) they will be counted as the same one.

pgp1
  • 524
  • look at the partition formula in wikipedia. – PNT Jun 14 '21 at 13:25
  • 1
    I don't think that there is an easy answer. –  Jun 14 '21 at 13:25
  • @Yassir: this question is more difficult than ordinary partitions. –  Jun 14 '21 at 13:27
  • oh, i didn't read the question carefully @YvesDaoust – PNT Jun 14 '21 at 13:29
  • 1
    @JMoravitz: no, $4$ is not allowed as a term. –  Jun 14 '21 at 13:30
  • 1
    @YvesDaoust I see that now. The question still remains though for clarification, does $2+1+1$ count as the "same" as $1+2+1$ or are they actually different? – JMoravitz Jun 14 '21 at 13:31
  • @JMoravitz: yes, this is an important distinction. Interestingly, for the ordinary partitions, if order does not matter, the problem is arduous. And if order matters, it becomes very easy. –  Jun 14 '21 at 13:32
  • If $2+1+1$ is considered the same as $1+2+1$ then the given example of $1,2,3$ being summed to $n$ can be seen via generating functions as the coefficient of $x^n$ in the expansion of $\frac{1}{(1-x)(1-x^2)(1-x^3)}=(1+x+x^2+x^3+x^4+\dots)(1+x^2+x^4+x^6+\dots)(1+x^3+x^6+x^9+\dots)$. If they are treated as different, then the number of ways $1,2,3$ can be summed to $n$ can be seen via recurrence relations with the Tribonacci sequence with initial conditions $f(-2)=f(-1)=0, f(0)=1$, and recurrence $f(n)=f(n-1)+f(n-2)+f(n-3)$ – JMoravitz Jun 14 '21 at 13:36

3 Answers3

2

There is a lot of work done by Ramanujan on this.

What you are looking for is called a "partition function" which has no closed form expression. A lot of work was done (and is being done) and it mostly involves complex analysis and generating functions.

See for further reading and a solid textbook this book by G. E. Andrews.

Edit: I looked through the textbook, and the generating function of the function $p(n) = \textrm{ nrways to partition } n \textrm{ from } i_1, i_2,... i_k$ is given by $\prod_{i_j} \frac{1}{(1-x^{i_j})}$ where each term is often denoted $(0:i_j)$.

Stefanos Van Dijk
  • 129
  • As I wrote in comments, this is not the ordinary partition function. –  Jun 14 '21 at 13:31
  • @YvesDaoust indeed, but work on the generating function of what you are looking for is also covered in the above book. It is not the standard partition function, but it is most definatelly a partition function. I believe chapter 4 if I am not mistaken. – Stefanos Van Dijk Jun 14 '21 at 13:54
  • Seems to be called a "restricted partition" in the general sense (because there are yet specialized versions of the restrictions). –  Jun 14 '21 at 13:59
  • @YvesDaoust Indeed. I took a course in this a few years ago, and we covered multiple different cases of restricted partitions. How many ways is there to partition a number such that the elements of the partition are 2 apart. 3 apart. etc etc – Stefanos Van Dijk Jun 14 '21 at 14:01
1

A simple recursive program to compute it starts with sorting the potential summands from largest to smallest. If you want the number of ways to sum to $10$ from $1,2,3$ you can write it as the number of ways to sum to $10-3=7$ from $3,2,1$ plus the number of ways to sum to $10$ from $2,1$. Each problem is simpler, so the recursion will terminate.

Ross Millikan
  • 374,822
  • This method enumerates all decompositions explicitly and this an exponential process. Can we do better ? –  Jun 14 '21 at 13:45
0

If you have k elements, you can calculate it in $O(kn)$ steps and $O(n)$ memory.
First $W(m,1)$ is how many ways just $a$ can sum to $m$, for all numbers $1\le m\le n$. $W(m,1)=W(m-a,1)$.
Second $W(m,2)$ uses just $a$ and $b$, $W(m,2)=W(m,1)+W(m-b,2)$. At this point you can throw away $W(m,1)$.
$W(m,3)=W(m,2)+W(m-c,3)$
Etc.

Empy2
  • 50,853