Partition (number theory)
In number theory and combinatorics, 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 the same partition. (If order matters, the sum becomes a composition.
For example, 4 can be partitioned in five distinct ways:
4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1
The order-dependent composition 1 + 3 is the same partition as 3 + 1, while the two distinct compositions 1 + 2 + 1 and 1 + 1 + 2 represent the same partition 2 + 1 + 1.
A summand in a partition is also called a part. The number of partitions of n is given by the partition function p(n). So p(4) = 5. The notation λ ⊢ n means that λ is a partition of n.
Partitions can be graphically visualized with Young diagrams or Ferrers 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.
See also
- Rank of a partition, a different notion of rank
- Crank of a partition
- Dominance order
- Factorization
- Integer factorization
- Partition of a set
- Stars and bars (combinatorics)
- Plane partition
- Polite number, defined by partitions into consecutive integers
- Multiplicative partition
- Twelvefold way
- Ewens's sampling formula
- Faà di Bruno's formula
- Multipartition
- Newton's identities
- Leibniz's distribution table for integer partitions
- Smallest-parts function
- A Goldbach partition is the partition of an even number into primes (see Goldbach's conjecture)
- Kostant's partition function