Partition function (number theory): Difference between revisions

Revision as of 22:48, 5 September 2003

Revision as of 22:46, 4 October 2003

Line 1:

The '''partition [[function]]''' p(''n'') is a [[multiplicative function|non-multiplicative function]] and represents the [[number]] of possible [[integer partition|partitions]] of a [[natural number]] ''n'', which is to say the number of distinct (and order independent) ways of representing ''n'' as a [[sum]] of natural numbers. By convention p(0)=1, p(<i>n</i>)=0 for <i>n</i> negative.

TheOne '''partition [[function]]''' p(''n'') is a [[multiplicative function|non-multiplicative function]] and represents the [[number]]way of possible [[integer partition|partitions]] ofgetting a [[naturalhandle number]] ''n'', which is to sayon the number of distinct (and order independent) ways of representing ''n'' as a [[sum]] of natural numbers. The partition function is easy to calculate. One way of doing so involves an intermediate function p(''k'',''n'') which represents the number of partitions of ''n'' using only natural numbers at least as large as ''k''. For any given value of ''k'', partitions counted by p(''k'',''n'') fit into exactly one of the following categories:

1. smallest [[addend]] is ''k''

Line 6 ⟶ 7:

2. smallest addend is [[strictly greater than]] than ''k''

The number of partitions meeting the first condition is p(''k'',''n''-''k''). IfTo the reason forsee this is not immediately apparent, imagine a list of all the partitions of the number ''n''-''k'' into numbers of size at least ''k'', then imagine appending "+''k''" to each partition in the list. Now what is it a list of?

The number of partitions meeting the second condition is p(''k''+1,''n''). Cansince anyonea explainpartition tointo usparts why?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''-''k''). The base cases of this [[recursion|recursive]] function are as follows:

Line 16 ⟶ 17:

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

This function willtends messto withexhibit one'sdeceptive [[mind]] if one lets itbehavior. Consider the following:

:p(1,4)=5

Line 24 ⟶ 25:

:p(5,20)=13

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

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

An alternative computation of the partition function involves [[generating function|generating functions]]. Consider the infinite product

<math>\prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right) </math>

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

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

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

Some values of the partition function are as follows:

*p(1)=1

*p(2)=2

*p(3)=3

*p(4)=5

*p(5)=7

*p(6)=11

*p(7)=15

*p(8)=22

*p(9)=30

*p(10)=42

*p(100)=190569292