[Math] In how many ways can we write $n$ as a sum of positive integers

combinatorics

In how many ways can we write $n$ as a sum of positive integers, where the order does not matter?

For example, 5 can be written as:

1+1+1+1+1

1+2+1+1 (This would be the same as 2+1+1+1.)

1+3+1

1+4

5

2+3

1+2+2

So, there are 7 ways (assuming I didn't miss anything!). How can we generalize this for any natural number $n$?

Best Answer

These are called integer partitions, and there are a lot of fun combinatorics that goes along with them. If we let $p(n)$ denote the number of integer partitions of $n$, the generating function is given by

$$ \sum_{n=0}^{\infty} p(n) x^n = \prod_{j=1}^{\infty}\frac{1}{1-x^j} $$

it's not too hard to convince yourself this is correct: the product on the right can be seen as

$$(1+x^{1\cdot1}+x^{2\cdot1}+x^{3 \cdot 1}+\dots)(1+x^{1\cdot2}+x^{2\cdot2}+x^{3\cdot 2}+\dots)(1+x^{1\cdot3}+x^{2\cdot3}+x^{3\cdot3}+\dots)\dots$$

so for example if we look at how one might get $x^5$:

  • $x^{1\cdot5} \iff 5$
  • $x^{1\cdot4} x^{1\cdot1} \iff 4 + 1$
  • $ x^{1\cdot3}x^{1\cdot2} \iff 3 + 2$
  • $ x^{1\cdot3}x^{2\cdot1} \iff 3 + 1 + 1$
  • $ x^{2\cdot2}x^{1\cdot1} \iff 2 + 2 + 1$
  • $ x^{1\cdot2}x^{3\cdot1} \iff 2 + 1 + 1 + 1$
  • $ x^{5\cdot1} \iff 1 +1+1+ 1 + 1$

and so $p(5) = 7$, as you enumerated.

Unfortunately there's no nice formula for this, but asymptotically we have

$$p(n) \sim \frac{e^{\sqrt n \,c}}{4\sqrt 3 \,n},$$

where $ c = \sqrt \frac{2}{3} \pi$. This is harder to prove, but I believe it is due to Hardy and Ramanujan.

Here is the most straightforward proof I could find, though it uses some results from Complex Analysis.

This is a proof using only real analysis, but the result is slightly weaker.

Related Question