Integer partition

<h2 id="examples">Examples</h2>
The seven partitions of 5 are

<ul><li>5</li>
<li>4 + 1</li>
<li>3 + 2</li>
<li>3 + 1 + 1</li>
<li>2 + 2 + 1</li>
<li>2 + 1 + 1 + 1</li>
<li>1 + 1 + 1 + 1 + 1</li></ul>
Some authors treat a partition as a non-increasing sequence of summands, rather than an expression with plus signs. For example, the partition 2 + 2 + 1 might instead be written as the <a href="/facts/Tuple/BI1HIxL8">tuple</a> (2, 2, 1) or in the even more compact form (22, 1) where the superscript indicates the number of repetitions of a part.
This multiplicity notation for a partition can be written alternatively as 
 
 
 
 
 1
 
 
 m
 
 1
 
 
 
 
 
 2
 
 
 m
 
 2
 
 
 
 
 
 3
 
 
 m
 
 3
 
 
 
 
 ⋯
 
 
 {\displaystyle 1^{m_{1}}2^{m_{2}}3^{m_{3}}\cdots }
 
, where m1 is the number of 1's, m2 is the number of 2's, etc. (Components with mi = 0 may be omitted.) For example, in this notation, the partitions of 5 are written 
 
 
 
 
 5
 
 1
 
 
 ,
 
 1
 
 1
 
 
 
 4
 
 1
 
 
 ,
 
 2
 
 1
 
 
 
 3
 
 1
 
 
 ,
 
 1
 
 2
 
 
 
 3
 
 1
 
 
 ,
 
 1
 
 1
 
 
 
 2
 
 2
 
 
 ,
 
 1
 
 3
 
 
 
 2
 
 1
 
 
 
 
 {\displaystyle 5^{1},1^{1}4^{1},2^{1}3^{1},1^{2}3^{1},1^{1}2^{2},1^{3}2^{1}}
 
, and 
 
 
 
 
 1
 
 5
 
 
 
 
 {\displaystyle 1^{5}}
 
.

<h2 id="diagrammatic-representations-of-partitions">Diagrammatic representations of partitions</h2>
There are two common diagrammatic methods to represent partitions: as Ferrers diagrams, named after <a href="/facts/Norman_Macleod_Ferrers/5LcJv1lR">Norman Macleod Ferrers</a>, and as Young diagrams, named after <a href="/facts/Alfred_Young_(mathematician)/L3R6cM6D">Alfred Young</a>. Both have several possible conventions; here, we use English notation, with diagrams aligned in the upper-left corner.

<h3>Ferrers diagram</h3>
The partition 6 + 4 + 3 + 1 of the number 14 can be represented by the following diagram:
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:

<table><tbody><tr><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>4</td><td>=</td><td>3 + 1</td><td>=</td><td>2 + 2</td><td>=</td><td>2 + 1 + 1</td><td>=</td><td>1 + 1 + 1 + 1</td></tr></tbody></table>
<h3>Young diagram</h3>
Main article: <a href="/facts/Young_diagram/e5lI4bck">Young diagram</a>
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

while the Ferrers diagram for the same partition is

<table><tbody><tr><td></td></tr></tbody></table>
While this seemingly trivial variation does not appear worthy of separate mention, Young diagrams turn out to be extremely useful in the study of <a href="/facts/Symmetric_functions/IB8N4T3m">symmetric functions</a> and <a href="/facts/Group_representation_theory/FsuuDagQ">group representation theory</a>: filling the boxes of Young diagrams with numbers (or sometimes more complicated objects) obeying various rules leads to a family of objects called <a href="/facts/Young_tableaux/e5lI4bck">Young tableaux</a>, and these tableaux have combinatorial and representation-theoretic significance.<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> As a type of shape made by adjacent squares joined together, Young diagrams are a special kind of <a href="/facts/Polyomino/XUlHFIRY">polyomino</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>

<h2 id="partition-function">Partition function</h2>

Main article: <a href="/facts/Partition_function_(number_theory)/mBUDy5vU">Partition function (number theory)</a>
The <a href="/facts/Partition_function_(number_theory)/mBUDy5vU">partition function</a> 
 
 
 
 p
 (
 n
 )
 
 
 {\displaystyle p(n)}
 
 counts the partitions of a non-negative integer 
 
 
 
 n
 
 
 {\displaystyle n}
 
. For instance, 
 
 
 
 p
 (
 4
 )
 =
 5
 
 
 {\displaystyle p(4)=5}
 
 because the integer 
 
 
 
 4
 
 
 {\displaystyle 4}
 
 has the five partitions 
 
 
 
 1
 +
 1
 +
 1
 +
 1
 
 
 {\displaystyle 1+1+1+1}
 
, 
 
 
 
 1
 +
 1
 +
 2
 
 
 {\displaystyle 1+1+2}
 
, 
 
 
 
 1
 +
 3
 
 
 {\displaystyle 1+3}
 
, 
 
 
 
 2
 +
 2
 
 
 {\displaystyle 2+2}
 
, and 
 
 
 
 4
 
 
 {\displaystyle 4}
 
.
The values of this function for 
 
 
 
 n
 =
 0
 ,
 1
 ,
 2
 ,
 …
 
 
 {\displaystyle n=0,1,2,\dots }
 
 are:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... (sequence A000041 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>).
The <a href="/facts/Generating_function/K7UVjnjL">generating function</a> of 
 
 
 
 p
 
 
 {\displaystyle p}
 
 is

∑
          
            n
            =
            0
          
          
            ∞
          
        
        p
        (
        n
        )
        
          q
          
            n
          
        
        =
        
          ∏
          
            j
            =
            1
          
          
            ∞
          
        
        
          ∑
          
            i
            =
            0
          
          
            ∞
          
        
        
          q
          
            j
            i
          
        
        =
        
          ∏
          
            j
            =
            1
          
          
            ∞
          
        
        (
        1
        −
        
          q
          
            j
          
        
        
          )
          
            −
            1
          
        
        .
      
    
    {\displaystyle \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}.}

No <a href="/facts/Closed-form_expression/y0xCXlSk">closed-form expression</a> for the partition function is known, but it has both <a href="/facts/Asymptotic_analysis/kt87qLpu">asymptotic expansions</a> that accurately approximate it and <a href="/facts/Recurrence_relation/JolXC71M">recurrence relations</a> by which it can be calculated exactly. It grows as an <a href="/facts/Exponential_function/ewlYxvR2">exponential function</a> of the <a href="/facts/Square_root/AfrzfBdQ">square root</a> of its argument.,<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> as follows:

p
        (
        n
        )
        ∼
        
          
            1
            
              4
              n
              
                
                  3
                
              
            
          
        
        exp
        ⁡
        
          (
          
            π
            
              
                
                  
                    2
                    n
                  
                  3
                
              
            
          
          )
        
      
    
    {\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)}
  
 as 
  
    
      
        n
        →
        ∞
      
    
    {\displaystyle n\to \infty }

In 1937, <a href="/facts/Hans_Rademacher/IXvTmDWY">Hans Rademacher</a> found a way to represent the partition function 
 
 
 
 p
 (
 n
 )
 
 
 {\displaystyle p(n)}
 
 by the <a href="/facts/Convergent_series/DTok170z">convergent series</a>

 
 
 
 p
 (
 n
 )
 =
 
 
 1
 
 π
 
 
 2
 
 
 
 
 
 
 ∑
 
 k
 =
 1
 
 
 ∞
 
 
 
 A
 
 k
 
 
 (
 n
 )
 
 
 k
 
 
 ⋅
 
 
 d
 
 d
 n
 
 
 
 
 (
 
 
 
 1
 
 n
 −
 
 
 1
 24
 
 
 
 
 
 sinh
 ⁡
 
 [
 
 
 
 
 π
 k
 
 
 
 
 
 
 2
 3
 
 
 
 (
 
 n
 −
 
 
 1
 24
 
 
 
 )
 
 
 
 
 
 
 
 
 ]
 
 
 )
 
 
 
 {\displaystyle 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)}

where

 
 
 
 
 A
 
 k
 
 
 (
 n
 )
 =
 
 ∑
 
 0
 ≤
 m
 <
 k
 ,
 
 (
 m
 ,
 k
 )
 =
 1
 
 
 
 e
 
 π
 i
 
 (
 
 s
 (
 m
 ,
 k
 )
 −
 2
 n
 m
 
 /
 
 k
 
 )
 
 
 
 .
 
 
 {\displaystyle A_{k}(n)=\sum _{0\leq m<k,\;(m,k)=1}e^{\pi i\left(s(m,k)-2nm/k\right)}.}

and 
 
 
 
 s
 (
 m
 ,
 k
 )
 
 
 {\displaystyle s(m,k)}
 
 is the <a href="/facts/Dedekind_sum/a56r07Vx">Dedekind sum</a>.
The <a href="/facts/Multiplicative_inverse/yczdYyCw">multiplicative inverse</a> of its generating function is the <a href="/facts/Euler_function/y6lE3VIL">Euler function</a>; by Euler's <a href="/facts/Pentagonal_number_theorem/z8TSDYAY">pentagonal number theorem</a> this function is an alternating sum of <a href="/facts/Pentagonal_number/P8pNBERv">pentagonal number</a> powers of its argument.

p
        (
        n
        )
        =
        p
        (
        n
        −
        1
        )
        +
        p
        (
        n
        −
        2
        )
        −
        p
        (
        n
        −
        5
        )
        −
        p
        (
        n
        −
        7
        )
        +
        ⋯
      
    
    {\displaystyle p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+\cdots }

<a href="/facts/Srinivasa_Ramanujan/HBPr4bzd">Srinivasa Ramanujan</a> discovered that the partition function has nontrivial patterns in <a href="/facts/Modular_arithmetic/0wtRa5dU">modular arithmetic</a>, now known as <a href="/facts/Ramanujan%2527s_congruences/HhcD7AFu">Ramanujan's congruences</a>. For instance, whenever the decimal representation of 
 
 
 
 n
 
 
 {\displaystyle n}
 
 ends in the digit 4 or 9, the number of partitions of 
 
 
 
 n
 
 
 {\displaystyle n}
 
 will be divisible by 5.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="restricted-partitions">Restricted partitions</h2>
In both combinatorics and number theory, families of partitions subject to various restrictions are often studied.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> This section surveys a few such restrictions.

<h3>Conjugate and self-conjugate partitions</h3>

If we flip the diagram of the partition 6 + 4 + 3 + 1 along its <a href="/facts/Main_diagonal/rkT2F08Q">main diagonal</a>, we obtain another partition of 14:

<table><tbody><tr><td></td><td>↔</td><td></td></tr><tr><td>6 + 4 + 3 + 1</td><td>=</td><td>4 + 3 + 3 + 2 + 1 + 1</td></tr></tbody></table>
By turning the rows into columns, we obtain the partition 4 + 3 + 3 + 2 + 1 + 1 of the number 14. Such partitions are said to be conjugate of one another.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> In the case of the number 4, partitions 4 and 1 + 1 + 1 + 1 are conjugate pairs, and partitions 3 + 1 and 2 + 1 + 1 are conjugate of each other. Of particular interest are partitions, such as 2 + 2, which have themselves as conjugate. Such partitions are said to be self-conjugate.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
Claim: The number of self-conjugate partitions is the same as the number of partitions with distinct odd parts.
Proof (outline): The crucial observation is that every odd part can be "folded" in the middle to form a self-conjugate diagram:

<table><tbody><tr><td></td><td>  ↔  </td><td></td></tr></tbody></table>
One can then obtain a <a href="/facts/Bijection/j4gTuTmW">bijection</a> between the set of partitions with distinct odd parts and the set of self-conjugate partitions, as illustrated by the following example:

<table><tbody><tr><td></td><td>↔</td><td></td></tr><tr><td>9 + 7 + 3</td><td>=</td><td>5 + 5 + 4 + 3 + 2</td></tr><tr><td>Dist. odd</td><td></td><td>self-conjugate</td></tr></tbody></table>
<h3>Odd parts and distinct parts </h3>
Among the 22 partitions of the number 8, there are 6 that contain only odd parts:

<ul><li>7 + 1</li>
<li>5 + 3</li>
<li>5 + 1 + 1 + 1</li>
<li>3 + 3 + 1 + 1</li>
<li>3 + 1 + 1 + 1 + 1 + 1</li>
<li>1 + 1 + 1 + 1 + 1 + 1 + 1 + 1</li></ul>
Alternatively, we could count partitions in which no number occurs more than once. Such a partition is called a partition with distinct parts. If we count the partitions of 8 with distinct parts, we also obtain 6:

<ul><li>8</li>
<li>7 + 1</li>
<li>6 + 2</li>
<li>5 + 3</li>
<li>5 + 2 + 1</li>
<li>4 + 3 + 1</li></ul>
This is a general property. For each positive number, the number of partitions with odd parts equals the number of partitions with distinct parts, denoted by q(n).<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> This result was proved by <a href="/facts/Leonhard_Euler/z2fsbjgj">Leonhard Euler</a> in 1748<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> and later was generalized as <a href="/facts/Glaisher%2527s_theorem/EoTXRHDg">Glaisher's theorem</a>.
For every type of restricted partition there is a corresponding function for the number of partitions satisfying the given restriction. An important example is q(n) (partitions into distinct parts). The first few values of q(n) are (starting with q(0)=1):

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ... (sequence A000009 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>).
The <a href="/facts/Generating_function/K7UVjnjL">generating function</a> for q(n) is given by<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

∑
          
            n
            =
            0
          
          
            ∞
          
        
        q
        (
        n
        )
        
          x
          
            n
          
        
        =
        
          ∏
          
            k
            =
            1
          
          
            ∞
          
        
        (
        1
        +
        
          x
          
            k
          
        
        )
        =
        
          ∏
          
            k
            =
            1
          
          
            ∞
          
        
        
          
            1
            
              1
              −
              
                x
                
                  2
                  k
                  −
                  1
                
              
            
          
        
        .
      
    
    {\displaystyle \sum _{n=0}^{\infty }q(n)x^{n}=\prod _{k=1}^{\infty }(1+x^{k})=\prod _{k=1}^{\infty }{\frac {1}{1-x^{2k-1}}}.}

The <a href="/facts/Pentagonal_number_theorem/z8TSDYAY">pentagonal number theorem</a> gives a recurrence for q:<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> 

q(k) = ak + q(k − 1) + q(k − 2) − q(k − 5) − q(k − 7) + q(k − 12) + q(k − 15) − q(k − 22) − ...
where ak is (−1)m if k = 3m2 − m for some integer m and is 0 otherwise.

<h3>Restricted part size or number of parts</h3>
Main article: <a href="/facts/Triangle_of_partition_numbers/U1o4SG83">Triangle of partition numbers</a>
By taking conjugates, the number pk(n) of partitions of n into exactly k parts is equal to the number of partitions of n in which the largest part has size k. The function pk(n) satisfies the recurrence

pk(n) = pk(n − k) + pk−1(n − 1)
with initial values p0(0) = 1 and pk(n) = 0 if n ≤ 0 or k ≤ 0 and n and k are not both zero.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
One recovers the function p(n) by

p
        (
        n
        )
        =
        
          ∑
          
            k
            =
            0
          
          
            n
          
        
        
          p
          
            k
          
        
        (
        n
        )
        .
      
    
    {\displaystyle p(n)=\sum _{k=0}^{n}p_{k}(n).}

One possible generating function for such partitions, taking k fixed and n variable, is

∑
          
            n
            ≥
            0
          
        
        
          p
          
            k
          
        
        (
        n
        )
        
          x
          
            n
          
        
        =
        
          x
          
            k
          
        
        
          ∏
          
            i
            =
            1
          
          
            k
          
        
        
          
            1
            
              1
              −
              
                x
                
                  i
                
              
            
          
        
        .
      
    
    {\displaystyle \sum _{n\geq 0}p_{k}(n)x^{n}=x^{k}\prod _{i=1}^{k}{\frac {1}{1-x^{i}}}.}

More generally, if T is a set of positive integers then the number of partitions of n, all of whose parts belong to T, has <a href="/facts/Generating_function/K7UVjnjL">generating function</a>

∏
          
            t
            ∈
            T
          
        
        (
        1
        −
        
          x
          
            t
          
        
        
          )
          
            −
            1
          
        
        .
      
    
    {\displaystyle \prod _{t\in T}(1-x^{t})^{-1}.}

This can be used to solve <a href="/facts/Change-making_problem/BaU0XNHl">change-making problems</a> (where the set T specifies the available coins). As two particular cases, one has that the number of partitions of n in which all parts are 1 or 2 (or, equivalently, the number of partitions of n into 1 or 2 parts) is

⌊
          
            
              
                n
                2
              
            
            +
            1
          
          ⌋
        
        ,
      
    
    {\displaystyle \left\lfloor {\frac {n}{2}}+1\right\rfloor ,}

and the number of partitions of n in which all parts are 1, 2 or 3 (or, equivalently, the number of partitions of n into at most three parts) is the nearest integer to (n + 3)2 / 12.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>

<h3>Partitions in a rectangle and Gaussian binomial coefficients</h3>
Main article: <a href="/facts/Gaussian_binomial_coefficient/AWfKqp7F">Gaussian binomial coefficient</a>
One may also simultaneously limit the number and size of the parts. Let p(N, M; n) denote the number of partitions of n with at most M parts, each of size at most N. Equivalently, these are the partitions whose Young diagram fits inside an M × N rectangle. There is a recurrence relation

p
        (
        N
        ,
        M
        ;
        n
        )
        =
        p
        (
        N
        ,
        M
        −
        1
        ;
        n
        )
        +
        p
        (
        N
        −
        1
        ,
        M
        ;
        n
        −
        M
        )
      
    
    {\displaystyle p(N,M;n)=p(N,M-1;n)+p(N-1,M;n-M)}

obtained by observing that 
 
 
 
 p
 (
 N
 ,
 M
 ;
 n
 )
 −
 p
 (
 N
 ,
 M
 −
 1
 ;
 n
 )
 
 
 {\displaystyle p(N,M;n)-p(N,M-1;n)}
 
 counts the partitions of n into exactly M parts of size at most N, and subtracting 1 from each part of such a partition yields a partition of n − M into at most M parts.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>
The Gaussian binomial coefficient is defined as:

(
              
              
                
                  k
                  +
                  ℓ
                
                ℓ
              
              
                )
              
            
          
          
            q
          
        
        =
        
          
            
              
                (
              
              
                
                  k
                  +
                  ℓ
                
                k
              
              
                )
              
            
          
          
            q
          
        
        =
        
          
            
              
                ∏
                
                  j
                  =
                  1
                
                
                  k
                  +
                  ℓ
                
              
              (
              1
              −
              
                q
                
                  j
                
              
              )
            
            
              
                ∏
                
                  j
                  =
                  1
                
                
                  k
                
              
              (
              1
              −
              
                q
                
                  j
                
              
              )
              
                ∏
                
                  j
                  =
                  1
                
                
                  ℓ
                
              
              (
              1
              −
              
                q
                
                  j
                
              
              )
            
          
        
        .
      
    
    {\displaystyle {k+\ell  \choose \ell }_{q}={k+\ell  \choose k}_{q}={\frac {\prod _{j=1}^{k+\ell }(1-q^{j})}{\prod _{j=1}^{k}(1-q^{j})\prod _{j=1}^{\ell }(1-q^{j})}}.}

The Gaussian binomial coefficient is related to the <a href="/facts/Generating_function/K7UVjnjL">generating function</a> of p(N, M; n) by the equality

∑
          
            n
            =
            0
          
          
            M
            N
          
        
        p
        (
        N
        ,
        M
        ;
        n
        )
        
          q
          
            n
          
        
        =
        
          
            
              
                (
              
              
                
                  M
                  +
                  N
                
                M
              
              
                )
              
            
          
          
            q
          
        
        .
      
    
    {\displaystyle \sum _{n=0}^{MN}p(N,M;n)q^{n}={M+N \choose M}_{q}.}

<h2 id="rank-and-durfee-square">Rank and Durfee square</h2>
Main article: <a href="/facts/Durfee_square/BdebsgX3">Durfee square</a>
The rank of a partition is the largest number k such that the partition contains at least k parts of size at least k. For example, the partition 4 + 3 + 3 + 2 + 1 + 1 has rank 3 because it contains 3 parts that are ≥ 3, but does not contain 4 parts that are ≥ 4. In the Ferrers diagram or Young diagram of a partition of rank r, the r × r square of entries in the upper-left is known as the <a href="/facts/Durfee_square/BdebsgX3">Durfee square</a>:

<table><tbody><tr><td></td></tr></tbody></table>
The Durfee square has applications within combinatorics in the proofs of various partition identities.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> It also has some practical significance in the form of the <a href="/facts/H-index/K9q5E93W">h-index</a>.
A different statistic is also sometimes called the <a href="/facts/Rank_of_a_partition/JSwNMVwB">rank of a partition</a> (or Dyson rank), namely, the difference 
 
 
 
 
 λ
 
 k
 
 
 −
 k
 
 
 {\displaystyle \lambda _{k}-k}
 
 for a partition of k parts with largest part 
 
 
 
 
 λ
 
 k
 
 
 
 
 {\displaystyle \lambda _{k}}
 
. This statistic (which is unrelated to the one described above) appears in the study of <a href="/facts/Ramanujan_congruences/HhcD7AFu">Ramanujan congruences</a>.

<h2 id="youngs-lattice">Young's lattice</h2>
Main article: <a href="/facts/Young%2527s_lattice/X90jpt0r">Young's lattice</a>
There is a natural <a href="/facts/Partial_order/qb4a3FAX">partial order</a> on partitions given by inclusion of Young diagrams. This partially ordered set is known as <a href="/facts/Young%2527s_lattice/X90jpt0r">Young's lattice</a>. The lattice was originally defined in the context of <a href="/facts/Representation_theory/3ydLtaGH">representation theory</a>, where it is used to describe the <a href="/facts/Irreducible_representation/Hu5geBgk">irreducible representations</a> of <a href="/facts/Symmetric_group/RUksK5l5">symmetric groups</a> Sn 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 <a href="/facts/Differential_poset/lVTzjYXy">differential poset</a>.

<h2 id="random-partitions">Random partitions</h2>
There is a deep theory of random partitions chosen according to the uniform probability distribution on the <a href="/facts/Symmetric_group/RUksK5l5">symmetric group</a> via the <a href="/facts/Robinson%25E2%2580%2593Schensted_correspondence/puYomvIg">Robinson–Schensted correspondence</a>. 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 <a href="/facts/Tracy%25E2%2580%2593Widom_distribution/kqYFk3SF">Tracy–Widom distribution</a>.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> <a href="/facts/Andrei_Okounkov/ME33ML8t">Okounkov</a> related these results to the combinatorics of <a href="/facts/Riemann_surface/qoj8ogv8">Riemann surfaces</a> and representation theory.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a><a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>

<h2 id="see-also">See also</h2>

Wikimedia Commons has media related to Integer partitions.

<ul><li><a href="/facts/Rank_of_a_partition/JSwNMVwB">Rank of a partition</a>, a different notion of rank</li>
<li><a href="/facts/Crank_of_a_partition/BFl4GazU">Crank of a partition</a></li>
<li><a href="/facts/Dominance_order/IMfAMRxS">Dominance order</a></li>
<li><a href="/facts/Factorization/tXrBXFh1">Factorization</a></li>
<li><a href="/facts/Integer_factorization/EjMCTz2t">Integer factorization</a></li>
<li><a href="/facts/Partition_of_a_set/VeP9g8CA">Partition of a set</a></li>
<li><a href="/facts/Stars_and_bars_(combinatorics)/UXptBeup">Stars and bars (combinatorics)</a></li>
<li><a href="/facts/Plane_partition/erlrREf2">Plane partition</a></li>
<li><a href="/facts/Polite_number/beKr1nnx">Polite number</a>, defined by partitions into consecutive integers</li>
<li><a href="/facts/Multiplicative_partition/yc9lQxmj">Multiplicative partition</a></li>
<li><a href="/facts/Twelvefold_way/uc32hbQj">Twelvefold way</a></li>
<li><a href="/facts/Ewens%2527s_sampling_formula/4mdbTdTj">Ewens's sampling formula</a></li>
<li><a href="/facts/Fa%25C3%25A0_di_Bruno%2527s_formula/F0RvTTQQ">Faà di Bruno's formula</a></li>
<li><a href="/facts/Multipartition/UXITNjwo">Multipartition</a></li>
<li><a href="/facts/Newton%2527s_identities/5J9flXxA">Newton's identities</a></li>
<li><a href="/facts/Spt_function/nYPMhc2H">Smallest-parts function</a></li>
<li>A Goldbach partition is the partition of an even number into primes (see <a href="/facts/Goldbach%2527s_conjecture/967UhtUU">Goldbach's conjecture</a>)</li>
<li><a href="/facts/Kostant%2527s_partition_function/V7Kl9507">Kostant's partition function</a></li></ul>

<h2 id="notes">Notes</h2>

<ul><li><a href="/facts/Milton_Abramowitz/6yRyez7P">Abramowitz, Milton</a>; <a href="/facts/Irene_Stegun/FjSS1LDR">Stegun, Irene</a> (1964). <a href="/facts/Abramowitz_and_Stegun/CNGSV3Ed">Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables</a>. United States Department of Commerce, National Bureau of Standards. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-486-61272-4. {{cite book}}: ISBN / Date incompatibility (help)</li>
<li><a href="/facts/George_E._Andrews/x58GmSuR">Andrews, George E.</a> (1976). The Theory of Partitions. Cambridge University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-63766-X.</li>
<li>Andrews, George E.; Eriksson, Kimmo (2004). Integer Partitions. Cambridge University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-60090-1.</li>
<li><a href="/facts/Tom_M._Apostol/S6vGtJWN">Apostol, Tom M.</a> (1990) [1976]. <a href="https://archive.org/details/modularfunctions0000apos">Modular functions and Dirichlet series in number theory</a>. <a href="/facts/Graduate_Texts_in_Mathematics/VTIfY29j">Graduate Texts in Mathematics</a>. Vol. 41 (2nd ed.). New York etc.: <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-97127-0. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0697.10023">0697.10023</a>. (See chapter 5 for a modern pedagogical intro to Rademacher's formula).</li>
<li><a href="/facts/Mikl%25C3%25B3s_B%25C3%25B3na/IyDujQwc">Bóna, Miklós</a> (2002). A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific Publishing. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 981-02-4900-4. (an elementary introduction to the topic of integer partitions, including a discussion of Ferrers graphs)</li>
<li><a href="/facts/G._H._Hardy/zBkDLb05">Hardy, G. H.</a>; <a href="/facts/E._M._Wright/SS01ywc2">Wright, E. M.</a> (2008) [1938]. An Introduction to the Theory of Numbers. Revised by <a href="/facts/Roger_Heath-Brown/uMHxGtbd">D. R. Heath-Brown</a> and <a href="/facts/Joseph_H._Silverman/acyPld7K">J. H. Silverman</a>. Foreword by <a href="/facts/Andrew_Wiles/bdc3k3pQ">Andrew Wiles</a>. (6th ed.). Oxford: <a href="/facts/Oxford_University_Press/CYyTzzWG">Oxford University Press</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-19-921986-5. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2445243">2445243</a>. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1159.11001">1159.11001</a>.</li>
<li><a href="/facts/D._H._Lehmer/EI61SICa">Lehmer, D. H.</a> (1939). <a href="https://doi.org/10.1090%2FS0002-9947-1939-0000410-9">"On the remainder and convergence of the series for the partition function"</a>. Trans. Amer. Math. Soc. 46: 362–373. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0002-9947-1939-0000410-9">10.1090/S0002-9947-1939-0000410-9</a>. <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0000410">0000410</a>. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0022.20401">0022.20401</a>. Provides the main formula (no derivatives), remainder, and older form for Ak(n).)</li>
<li>Gupta, Hansraj; Gwyther, C.E.; Miller, J.C.P. (1962). Royal Society of Math. Tables. Vol. 4, Tables of partitions. (Has text, nearly complete bibliography, but they (and Abramowitz) missed the Selberg formula for Ak(n), which is in Whiteman.)</li>
<li><a href="/facts/Ian_G._Macdonald/PoaeNbeg">Macdonald, Ian G.</a> (1979). Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. <a href="/facts/Oxford_University_Press/CYyTzzWG">Oxford University Press</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-19-853530-9. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0487.20007">0487.20007</a>. (See section I.1)</li>
<li>Nathanson, M.B. (2000). Elementary Methods in Number Theory. Graduate Texts in Mathematics. Vol. 195. <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-98912-9. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0953.11002">0953.11002</a>.</li>
<li><a href="/facts/Hans_Rademacher/IXvTmDWY">Rademacher, Hans</a> (1974). Collected Papers of Hans Rademacher. Vol. v II. MIT Press. pp. 100–07, 108–22, 460–75.</li>
<li><a href="/facts/Marcus_du_Sautoy/7LabtSsz">Sautoy, Marcus Du.</a> (2003). <a href="https://archive.org/details/musicofprimessea00dusa">The Music of the Primes</a>. New York: Perennial-HarperCollins. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9780066210704.</li>
<li><a href="/facts/Richard_P._Stanley/8bQ4QrLM">Stanley, Richard P.</a> (1999). <a href="http://www-math.mit.edu/~rstan/ec/">Enumerative Combinatorics</a>. Vol. 1 and 2. Cambridge University Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-56069-1.</li>
<li>Whiteman, A. L. (1956). <a href="http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1103044252">"A sum connected with the series for the partition function"</a>. Pacific Journal of Mathematics. 6 (1): 159–176. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2140%2Fpjm.1956.6.159">10.2140/pjm.1956.6.159</a>. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0071.04004">0071.04004</a>. (Provides the Selberg formula. The older form is the finite Fourier expansion of Selberg.)</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.encyclopediaofmath.org/index.php?title=Partition">"Partition"</a>, <a href="/facts/Encyclopedia_of_Mathematics/WC6mGtPm">Encyclopedia of Mathematics</a>, <a href="/facts/European_Mathematical_Society/B3h7b672">EMS Press</a>, 2001 [1994]</li>
<li><a href="http://www.se16.info/js/partitions.htm">Partition and composition calculator</a></li>
<li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/Partition.html">"Partition"</a>. <a href="/facts/MathWorld/yc1jodbq">MathWorld</a>.</li>
<li>Wilf, Herbert S. <a href="http://www.math.upenn.edu/%7Ewilf/PIMS/PIMSLectures.pdf">Lectures on Integer Partitions</a> (PDF), <a href="https://web.archive.org/web/20210224220544if_/https://www.math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf">archived</a> (PDF) from the original on 2021-02-24, retrieved 2021-02-28</li>
<li><a href="http://www.luschny.de/math/seq/CountingWithPartitions.html">Counting with partitions</a> with reference tables to the On-Line Encyclopedia of Integer Sequences</li>
<li><a href="http://www.findstat.org/IntegerPartitions">Integer partitions</a> entry in the <a href="http://www.findstat.org/">FindStat</a> database</li>
<li><a href="http://metacpan.org/module/Integer::Partition">Integer::Partition Perl module</a> from <a href="/facts/CPAN/MB7Iv662">CPAN</a></li>
<li><a href="https://web.archive.org/web/20090220004749/http://www.site.uottawa.ca/~ivan/F49-int-part.pdf">Fast Algorithms For Generating Integer Partitions</a></li>
<li><a href="https://arxiv.org/abs/0909.2331">Generating All Partitions: A Comparison Of Two Encodings</a></li>
<li>Grime, James (April 28, 2016). <a href="https://www.youtube.com/watch?v=NjCIq58rZ8I">"Partitions - Numberphile"</a> (video). <a href="/facts/Brady_Haran/7oNb0Tez">Brady Haran</a>. <a href="https://ghostarchive.org/varchive/youtube/20211211/NjCIq58rZ8I">Archived</a> from the original on 2021-12-11. Retrieved 5 May 2016.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Andrews 1976, p. 199. - Andrews, George E. (1976). The Theory of Partitions. Cambridge University Press. ISBN 0-521-63766-X. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Josuat-Vergès, Matthieu (2010), "Bijections between pattern-avoiding fillings of Young diagrams", Journal of Combinatorial Theory, Series A, 117 (8): 1218–1230, arXiv:0801.4928, doi:10.1016/j.jcta.2010.03.006, MR 2677686, S2CID 15392503. <a href="/wiki/Journal_of_Combinatorial_Theory" target="_blank">/wiki/Journal_of_Combinatorial_Theory</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Andrews 1976, p. 69. - Andrews, George E. (1976). The Theory of Partitions. Cambridge University Press. ISBN 0-521-63766-X. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Hardy & Wright 2008, p. 380. - Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001.Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2445243" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=2445243</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Alder, Henry L. (1969). "Partition identities - from Euler to the present". American Mathematical Monthly. 76 (7): 733–746. doi:10.2307/2317861. JSTOR 2317861. <a href="http://www.maa.org/programs/maa-awards/writing-awards/partition-identities-from-euler-to-the-present" target="_blank">http://www.maa.org/programs/maa-awards/writing-awards/partition-identities-from-euler-to-the-present</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Hardy & Wright 2008, p. 362. - Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001.Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2445243" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=2445243</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Hardy & Wright 2008, p. 368. - Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001.Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2445243" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=2445243</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Hardy & Wright 2008, p. 365. - Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001.Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001. <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2445243" target="_blank">https://mathscinet.ams.org/mathscinet-getitem?mr=2445243</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Notation follows Abramowitz & Stegun 1964, p. 825 - Abramowitz, Milton; Stegun, Irene (1964). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. United States Department of Commerce, National Bureau of Standards. ISBN 0-486-61272-4. <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Andrews, George E. (1971). Number Theory. Philadelphia: W. B. Saunders Company. pp. 149–50. <a href="/wiki/George_Andrews_(mathematician)" target="_blank">/wiki/George_Andrews_(mathematician)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Abramowitz & Stegun 1964, p. 825, 24.2.2 eq. I(B) - Abramowitz, Milton; Stegun, Irene (1964). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. United States Department of Commerce, National Bureau of Standards. ISBN 0-486-61272-4. <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Abramowitz & Stegun 1964, p. 826, 24.2.2 eq. II(A) - Abramowitz, Milton; Stegun, Irene (1964). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. United States Department of Commerce, National Bureau of Standards. ISBN 0-486-61272-4. <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Richard Stanley, Enumerative Combinatorics, volume 1, second edition. Cambridge University Press, 2012. Chapter 1, section 1.7. <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Hardy, G.H. (1920). Some Famous Problems of the Theory of Numbers. Clarendon Press. <a href="https://archive.org/details/in.ernet.dli.2015.84630" target="_blank">https://archive.org/details/in.ernet.dli.2015.84630</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Andrews 1976, pp. 33–34. - Andrews, George E. (1976). The Theory of Partitions. Cambridge University Press. ISBN 0-521-63766-X. <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">see, e.g., Stanley 1999, p. 58 - Stanley, Richard P. (1999). Enumerative Combinatorics. Vol. 1 and 2. Cambridge University Press. ISBN 0-521-56069-1. <a href="http://www-math.mit.edu/~rstan/ec/" target="_blank">http://www-math.mit.edu/~rstan/ec/</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Romik, Dan (2015). The surprising mathematics of longest increasing subsequences. Institute of Mathematical Statistics Textbooks. New York: Cambridge University Press. ISBN 978-1-107-42882-9. <a href="978-1-107-42882-9" target="_blank">978-1-107-42882-9</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Okounkov, Andrei (2000). "Random matrices and random permutations". International Mathematics Research Notices. 2000 (20): 1043. doi:10.1155/S1073792800000532. S2CID 14308256.{{cite journal}}: CS1 maint: unflagged free DOI (link) <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Okounkov, A. (2001-04-01). "Infinite wedge and random partitions". Selecta Mathematica. 7 (1): 57–81. arXiv:math/9907127. doi:10.1007/PL00001398. ISSN 1420-9020. S2CID 119176413. <a href="https://doi.org/10.1007/PL00001398" target="_blank">https://doi.org/10.1007/PL00001398</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
</ol>

Integer partition open-in-new

Integer partition