Partition function (number theory): Difference between revisions

Revision as of 22:48, 3 January 2005

Revision as of 03:38, 23 March 2005

Line 1:

TheIn [[number theory]], the '''partition [[function (mathematics)|function]]''' p(''n'') 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. For example, 4 can be partitioned in 5 distinct ways
:4, 3+1, 2+2, 2+1+1, 1+1+1+1
So p(4) = 5. By convention p(0) = 1, p(''n'') = 0 for ''n'' negative.

==Intermediate function==

One way of getting a handle on the partition function 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:

Line 27 ⟶ 31:

Our original function p(''n'') is just p(1, ''n'').

==Generating function==

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

A [[generating function]] for p(''n'') is given by

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

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

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

Expanding each term on the right-hand side as a [[geometric series]], we can rewrite it as

:(1 + ''x'' + ''x''² + ''x''³ + ...)(1 + ''x''² + ''x''⁴ + ''x''⁶ + ...)(1 + ''x''³ + ''x''⁶ + ''x''⁹ + ...) ...

Line 46 ⟶ 52:

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;, +, +, ...

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

==Table of values==

Some values of the partition function are as follows:

Line 62 ⟶ 72:

*p(1000) = 24061467864032622473692149727991

*p(10000) = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144

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

==See also==

[[number theory]]

==External links==

Line 77 ⟶ 81:

[[Category:Number theory]]

[[sv:Partitionsfunktionen]]