Integer partition: Difference between revisions

Revision as of 00:44, 18 June 2024

Latest revision as of 16:38, 24 July 2025

(21 intermediate revisions by 15 users not shown)

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 124 ⟶ 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 150 ⟶ 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 251 ⟶ 252:

== 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 asympototicallyasymptotically 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 |url=https://academic.oup.com/imrn/article-lookup/doi/10.1155/S1073792800000532 |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 307 ⟶ 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| ]]