Editing Integer partition (section)

==Partition function==
[[File:Euler_partition_function.svg|thumb|upright|link={{filepath:Euler_partition_function.svg}}|Using Euler's method to find ''p''(40): A ruler with plus and minus signs (grey box) is slid downwards, the relevant parts added or subtracted. The positions of the signs are given by differences of alternating natural (blue) and odd (orange) numbers. In [{{filepath:Euler_partition_function.svg}} the SVG file,] hover over the image to move the ruler.]]
{{main|Partition function (number theory)}}
The [[Partition function (number theory)|partition function]] <math>p(n)</math> counts the partitions of a non-negative integer <math>n</math>. For instance, <math>p(4)=5</math> because the integer <math>4</math> has the five partitions <math>1+1+1+1</math>, <math>1+1+2</math>, <math>1+3</math>, <math>2+2</math>, and <math>4</math>.
The values of this function for <math>n=0,1,2,\dots</math> are:
:1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... {{OEIS|id=A000041}}.

The [[generating function]] of <math>p</math> is 
:<math>\sum_{n=0}^{\infty}p(n)q^n=\prod_{j=1}^{\infty}\sum_{i=0}^{\infty}q^{ji}=\prod_{j=1}^{\infty}(1-q^j)^{-1}.</math>

No [[closed-form expression]] for the partition function is known, but it has both [[asymptotic analysis|asymptotic expansions]] that accurately approximate it and [[recurrence relation]]s by which it can be calculated exactly. It grows as an [[exponential function]] of the [[square root]] of its argument.,{{sfn|Andrews|1976|p=69}} as follows:

:<math>p(n) \sim \frac {1} {4n\sqrt3} \exp\left({\pi \sqrt {\frac{2n}{3}}}\right)</math> as <math>n \to \infty</math>

In 1937, [[Hans Rademacher]] found a way to represent the partition function <math>p(n)</math> by the [[convergent series]]

<math display="block">p(n) = \frac{1}{\pi \sqrt{2}} \sum_{k=1}^\infty A_k(n)\sqrt{k} \cdot
\frac{d}{dn} \left({
    \frac {1} {\sqrt{n-\frac{1}{24}}}
    \sinh \left[ {\frac{\pi}{k}
    \sqrt{\frac{2}{3}\left(n-\frac{1}{24}\right)}}\,\,\,\right]
}\right)</math>
where

<math display="block">A_k(n) = \sum_{0 \le m < k, \; (m, k) = 1}
e^{ \pi i \left( s(m, k) - 2 nm/k \right) }.</math>
and <math>s(m,k)</math> is the [[Dedekind sum]].

The [[multiplicative inverse]] of its generating function is the [[Euler function]]; by Euler's [[pentagonal number theorem]] this function is an alternating sum of [[pentagonal number]] powers of its argument.

:<math>p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+\cdots</math>

[[Srinivasa Ramanujan]] discovered that the partition function has nontrivial patterns in [[modular arithmetic]], now known as [[Ramanujan's congruences]]. For instance, whenever the decimal representation of <math>n</math> ends in the digit 4 or 9, the number of partitions of <math>n</math> will be divisible by 5.{{sfn|Hardy|Wright|2008|p=380}}