Partition function (number theory): Difference between revisions

Revision as of 09:01, 2 January 2005

Revision as of 22:45, 3 January 2005

Line 10:

The number of partitions meeting the second condition is p(''k''+1,''n'') since a partition into parts of at least <i>k</i> which contains no parts of at exactly <i>k</i> must have all parts at least <i>k+1</i>.

Since the two conditions are [[mutually exclusive]], the number of partitions meeting either condition is p(''k''+1, ''n'') + p(''k'', ''n''- &minus; ''k''). The base cases of this [[recursion|recursive]] function are as follows:

* p(''k'', ''n'') = 0 if ''k'' > ''n''

* p(''k'', ''n'') = 1 if ''k'' = ''n''

This function tends to exhibit deceptive behavior.

:p(1, 4) = 5

:p(2, 8) = 7

:p(3, 12) = 9

:p(4, 16) = 11

:p(5, 20) = 13

:p(6, 24) = '''16'''

Our original function p(<i>n</i>) is just p(1,<i>n</i>).

Line 33:

Expanding each term as a [[geometric series]], we can rewrite it as

:(1 + <i>''x</i>'' + <i>''x</i>''² + <i>''x</i>''³ + ...)(1 + <i>''x</i>''² + <i>''x</i>''⁴ + <i>''x</i>''⁶ + ...)(1 + <i>''x</i>''³ + <i>''x</i>''⁶ + <i>''x</i>''⁹ + ...) ...

The <i>''x</i>''^''m'' term in this product counts the number of ways to write

:<i>''n</i>'' = <i>''a</i>''₁ + 2<i>''a</i>''₂ + 3<i>''a</i>''₃ + ... = (1 + 1 + 1 + 1 + ...) + (2 + 2 + 2 + 2 + ...) + (3 + 3 + 3 ...) + ...,

where each number <''i>i</i>'' appears <i>''a</i>''_''i'' times. This is precisely the definition of a partition of <i>''n</i>'', so our product is the desired generating function. More generally, the generating function for the partitions of <i>''n</i>'' into numbers from a set <i>''A</i>'' can be found by taking only those terms in the product where <i>''k</i>'' is an element of <i>''A</i>''. This result is due to [[Leonhard Euler|Euler]].

The formulation of the generating function is similar to the product formulation of many [[modular form|modular forms]], giving some idea of the connection between the two. It can also be used in conjunction with the [[pentagonal number theorem]] to derive a recurrence for the partition function stating that

Line 45:

p(<i>k</i>) &minus; p(<i>k</i>&minus; 1) &minus; p(''k'' &minus; 2) + p(''k'' &minus; 5) + p(''k'' &minus; 7) - p(''k'' &minus; 12) &minus; ... = 0,

where the sum is taken over all [[polygonal number|pentagonal numbers]] of the form ½''n''(3''n'' &minus; 1), including those where ''n'' < 0, and the terms continue to alternate +, +, -&minus;, -&minus;, +, +, ...

Some values of the partition function are as follows:

Line 63:

*p(10000) = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144

Euler's generating function is a special case of a [[Q-series|q-series]] and is closely related to the [[Dedekind eta function]].

==See also ==

[[number theory]].

==External links==