Integer partition: Difference between revisions

Revision as of 04:58, 25 October 2024

Revision as of 18:27, 25 October 2024

Line 4:

[[File:Partitions of n with biggest addend k.svg|thumb|right|300px|Partitions of {{mvar|n}} with largest part {{mvar|k}}]]

In [[number theory]] and [[combinatorics]], a '''partition''' of a non-negative [[integer]] {{mvar|n}}, also called an '''integer partition''', is a way of writing {{mvar|n}} as a [[summation|sum]] of [[positive integers]]. Two sums that differ only in the order of their [[summand]]s (the numbers to be added; an individual summand in a partition is called a '''part''') are considered the same partition. (If order matters, the sum becomes a [[composition (combinatorics)|composition]].) For example, {{math|4}} can be partitioned in five distinct ways:

:{{math|4}}

Line 12:

:{{math|1 + 1 + 1 + 1}}

By contrast, theThe only partition of zero is the empty sum, having no parts.

The order-dependent composition {{math|1 + 3}} is the same partition as {{math|3 + 1}}, and the two distinct compositions {{math|1 + 2 + 1}} and {{math|1 + 1 + 2}} represent the same partition as {{math|2 + 1 + 1}}.

An individual summand in a partition is called a '''part'''. The number of partitions of {{mvar|n}} is given by the [[Partition function (number theory)|partition function]] {{math|''p''(''n'')}}. So {{math|1=''p''(4) = 5}}. The notation {{math|''λ'' ⊢ ''n''}} means that {{mvar|λ}} is a partition of {{mvar|n}}.

Partitions can be graphically visualized with [[Young diagram]]s or [[Ferrers diagram]]s. They occur in a number of branches of [[mathematics]] and [[physics]], including the study of [[symmetric polynomial]]s and of the [[symmetric group]] and in [[group representation|group representation theory]] in general.