Given a natural number n, how do we find the recurrence for the number of distinct partitions of the number? Note: 4 -> {4},{3,1},{2,2},{1,1,1,1},{2,1,1} Here, {1,3} and {3,1} are the considered the same Also, can we get a closed form for the recurrence?



1 Answer 1


The Online Encyclopedia of Integer Sequences is a great place to look for this sort of thing.

There are explicit functions, like Rademacher's formula which can be truncated to give very accurate asymptotics. There are also many recurrence relations, all of which you can find an overview of on Wolfram Mathworld.

In both cases the link will take you to the entry on the 'partition function', which is the name of what you are asking about.

  • 1
    $\begingroup$ There is no known explicit formula? There is Rademacher's exact formula and more, see here. $\endgroup$ Commented Nov 2, 2016 at 20:16
  • $\begingroup$ @DietrichBurde Thanks for the link, the Folsom-Masri paper from that link gives a nice exposition about exact formulae. $\endgroup$
    – Mathily
    Commented Nov 2, 2016 at 20:46
  • $\begingroup$ Yes, this is a nice paper! $\endgroup$ Commented Nov 2, 2016 at 20:58

Not the answer you're looking for? Browse other questions tagged .