Partition (number theory)

related topics
{math, number, function}
{style, bgcolor, rowspan}
{area, part, region}
{son, year, death}
{math, energy, light}

In number theory, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a composition. A summand in a partition is also called a part. The number of partitions of n is given by the partition function p(n).

Contents

Examples

The partitions of 4 are listed below:

The partitions of 8 are listed below:

Partition function

In number theory, the partition function p(n) represents the number of possible 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 five distinct ways:

The order dependent composition 1 + 3 is the same partition as 3 + 1, while 1 + 2 + 1 and 1 + 1 + 2 are the same partition as 2 + 1 + 1.

So p(4) = 5. By convention p(0) = 1, p(n) = 0 for n negative. Partitions can be graphically visualized with Young diagrams. They occur in a number of branches of mathematics and physics, including the study of symmetric polynomials, the symmetric group and in group representation theory in general.

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:

The number of partitions meeting the first condition is p(kn − k). To see this, 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? As a side note, one can use this to define a sort of recursion relation for the partition function in term of the intermediate function, namely

Full article ▸

related documents
Ultrafilter
Absolute convergence
Complex analysis
Natural transformation
Gaussian quadrature
Countable set
Galois theory
Exclusive or
Sequence
Elliptic curve
Ideal class group
IEEE 754-1985
Filter (mathematics)
Modular arithmetic
Linear combination
Algebraic structure
Semigroup
Database normalization
XPath 1.0
E (mathematical constant)
Random variable
Abstract interpretation
Homological algebra
Key size
Scope (programming)
Fuzzy logic
Binary relation
Tychonoff's theorem
Pushdown automaton
Ordinary differential equation