Integer partition: Difference between revisions

Revision as of 18:13, 19 November 2023

Latest revision as of 16:38, 24 July 2025

(39 intermediate revisions by 24 users not shown)

Line 1:

{{short description|Decomposition of an integer as a sum of positive integers}}

{{about|partitioning an integer|grouping elements of a set|Partition of a set|the partition calculus of sets|Infinitary combinatorics|the problem of partitioning a multiset of integers so that each part has the same sum|Partition problem}}

[[File:Ferrer partitioning diagrams.svg|thumb|right|300px|[[Young diagram#Diagrams|Young diagrams]] associated to the partitions of the positive integers 1 through 8. They are arranged so that images under the reflection about the main diagonal of the square are conjugate partitions.]]

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

Line 20:

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.

==8Examples==

The seven partitions of 5 are

* 5

Line 30:

* 1 + 1 + 1 + 1 + 1

Some authors treat a partition as a decreasingnon-increasing sequence of summands, rather than an expression with plus signs. For example, the partition 2 + 2 + 1 might instead be written as the [[tuple]] {{math|(2, 2, 1)}} or in the even more compact form {{math|(2², 1)}} where the superscript indicates the number of repetitions of a part.

This multiplicity notation for a partition can be written alternatively as <math>1^{m_1}2^{m_2}3^{m_3}\cdots</math>, where {{math|''m''₁}} is the number of 1's, {{math|''m''₂}} is the number of 2's, etc. (Components with {{math|''m''_''i'' {{=}} 0}} may be omitted.) For example, in this notation, the partitions of 5 are written <math>5^1, 1^1 4^1, 2^1 3^1, 1^2 3^1, 1^1 2^2, 1^3 2^1</math>, and <math>1^5</math>.

Line 42:

[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br/>[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]

The 14 circles are lined up in 4 rows, each having the size of a part of the partition.
The diagrams for the 5 partitions of the number 4 are shown below:

{|

Line 61 ⟶ 62:

===Young diagram===

{{Main|Young diagram}}

An alternative visual representation of an integer partition is its ''Young diagram'' (often also called a Ferrers diagram). Rather than representing a partition with dots, as in the Ferrers diagram, the Young diagram uses boxes or squares. Thus, the Young diagram for the partition 5 + 4 + 1 is

:[[Image:Young diagram for 541 partition.svg|100px]]

Line 94 ⟶ 96:

:<math>\sum_{n=0}^{\infty}p(n)q^n=\prod_{j=1}^{\infty}\sum_{i=0}^{\infty}q^{ji}=\prod_{j=1}^{\infty}(1-q^j)^{-1}.</math>

No [[closed-form expression]] for the partition function is known, but it has both [[asymptotic analysis|asymptotic expansions]] that accurately approximate it and [[recurrence relation]]s by which it can be calculated exactly. It grows as an [[exponential function]] of the [[square root]] of its argument.,{{sfn|Andrews|1976|p=69}}, as follows:

:<math>p(n) \sim \frac {1} {4n\sqrt3} \exp\left({\pi \sqrt {\frac{2n}{3}}}\right)</math> as <math>n \to \infty</math>

In 1937, [[Hans Rademacher]] found a way to represent the partition function <math>p(n)</math> by the [[convergent series]]

<math display="block">p(n) = \frac{1}{\pi \sqrt{2}} \sum_{k=1}^\infty A_k(n)\sqrt{k} \cdot

\frac{d}{dn} \left({

\frac {1} {\sqrt{n-\frac{1}{24}}}

\sinh \left[ {\frac{\pi}{k}

\sqrt{\frac{2}{3}\left(n-\frac{1}{24}\right)}}\,\,\,\right]

}\right)</math>

where

<math display="block">A_k(n) = \sum_{0 \le m < k, \; (m, k) = 1}

e^{ \pi i \left( s(m, k) - 2 nm/k \right) }.</math>

and <math>s(m,k)</math> is the [[Dedekind sum]].

The [[multiplicative inverse]] of its generating function is the [[Euler function]]; by Euler's [[pentagonal number theorem]] this function is an alternating sum of [[pentagonal number]] powers of its argument.

Line 109 ⟶ 125:

===Conjugate and self-conjugate partitions===

{{anchor|Conjugate partitions}}

If we flip the diagram of the partition 6 + 4 + 3 + 1 along its [[main diagonal]], we obtain another partition of 14:

{|

Line 135 ⟶ 151:

|}

One can then obtain a [[bijection]] between the set of partitions with distinct odd parts and the set of self-conjugate partitions, as illustrated by the following example:

{|

Line 234 ⟶ 250:

{{main|Young's lattice}}

There is a natural [[partial order]] on partitions given by inclusion of Young diagrams. This partially ordered set is known as ''[[Young's lattice]]''. The lattice was originally defined in the context of [[representation theory]], where it is used to describe the [[irreducible representation]]s of [[symmetric group]]s ''S''_''n'' for all ''n'', together with their branching properties, in characteristic zero. It also has received significant study for its purely combinatorial properties; notably, it is the motivating example of a [[differential poset]].

== Random partitions ==

There is a deep theory of random partitions chosen according to the uniform probability distribution on the [[symmetric group]] via the [[Robinson–Schensted correspondence]]. In 1977, Logan and Shepp, as well as Vershik and Kerov, showed that the Young diagram of a typical large partition becomes asymptotically close to the graph of a certain analytic function minimizing a certain functional. In 1988, Baik, Deift and Johansson extended these results to determine the distribution of the longest increasing subsequence of a random permutation in terms of the [[Tracy–Widom distribution]].<ref>{{Cite book |last=Romik |first=Dan |title=The surprising mathematics of longest increasing subsequences |date=2015 |publisher=Cambridge University Press |isbn=978-1-107-42882-9 |series=Institute of Mathematical Statistics Textbooks |___location=New York}}</ref> [[Andrei Okounkov|Okounkov]] related these results to the combinatorics of [[Riemann surface]]s and representation theory.<ref>{{Cite journal |last=Okounkov |first=Andrei |date=2000 |title=Random matrices and random permutations |journal=International Mathematics Research Notices |volume=2000 |issue=20 |pages=1043 |doi=10.1155/S1073792800000532 |doi-access=<!-- not free-->|s2cid=14308256 }}</ref><ref>{{Cite journal |last=Okounkov |first=A. |date=2001-04-01 |title=Infinite wedge and random partitions |url=https://doi.org/10.1007/PL00001398 |journal=Selecta Mathematica |language=en |volume=7 |issue=1 |pages=57–81 |doi=10.1007/PL00001398 |s2cid=119176413 |issn=1420-9020|arxiv=math/9907127 }}</ref>

== See also ==

Line 289 ⟶ 308:

* {{cite web|last1=Grime|first1=James|title=Partitions - Numberphile|url=https://www.youtube.com/watch?v=NjCIq58rZ8I| archive-url=https://ghostarchive.org/varchive/youtube/20211211/NjCIq58rZ8I| archive-date=2021-12-11 | url-status=live|publisher=[[Brady Haran]]|access-date=5 May 2016|format=video|date=April 28, 2016}}{{cbignore}}

{{DEFAULTSORT:Partition (Number Theory)}}

[[Category:Integer partitions| ]]