Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Rank of a partition
open-in-new
<h2 id="definition">Definition</h2> <p>By a <i><a href="/facts/Integer_partition/LtyXWqwH">partition</a></i> of a positive integer <i>n</i> we mean a finite multiset λ = { λ<i>k</i>, λ<i>k</i> − 1, . . . , λ1 } of positive integers satisfying the following two conditions: </p> <ul><li>λk ≥ . . . ≥ λ2 ≥ λ1 > 0.</li> <li><i>λ</i><i>k</i> + . . . + λ2 + λ1 = <i>n</i>.</li></ul> <p>If <i>λ</i><i>k</i>, . . . , <i>λ</i>2, <i>λ</i>1 are distinct, that is, if </p> <ul><li><i>λ</i><i>k</i> > . . . > λ2 > λ1 > 0</li></ul> <p>then the partition <i>λ</i> is called a <i>strict partition</i> of <i>n</i>. The integers <i>λ</i><i>k</i>, λ<i>k</i> − 1, ..., <i>λ</i>1 are the <i>parts</i> of the partition. The number of parts in the partition <i>λ</i> is <i>k</i> and the largest part in the partition is <i>λ</i><i>k</i>. The rank of the partition <i>λ</i> (whether ordinary or strict) is defined as <i>λ</i><i>k</i> − <i>k</i>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> </p><p>The ranks of the partitions of <i>n</i> take the following values and no others:<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <i>n</i> − 1, <i>n</i> −3, <i>n</i> −4, . . . , 2, 1, 0, −1, −2, . . . , −(<i>n</i> − 4), −(<i>n</i> − 3), −(<i>n</i> − 1). <p>The following table gives the ranks of the various partitions of the number 5. </p> <p>Ranks of the partitions of the integer 5 </p> <table><tbody><tr><th>Partition (λ)</th><th>Largest part (<i>λ</i><i>k</i>)</th><th>Number of parts (<i>k</i>)</th><th>Rank of the partition (<i>λ</i><i>k</i> − <i>k</i> )</th></tr><tr><td>{ 5 }</td><td>5</td><td>1</td><td>4</td></tr><tr><td>{ 4, 1 }</td><td>4</td><td>2</td><td>2</td></tr><tr><td>{ 3, 2 }</td><td>3</td><td>2</td><td>1</td></tr><tr><td>{ 3, 1, 1 }</td><td>3</td><td>3</td><td>0</td></tr><tr><td>{ 2, 2, 1 }</td><td>2</td><td>3</td><td>−1</td></tr><tr><td>{ 2, 1, 1, 1 }</td><td>2</td><td>4</td><td>−2</td></tr><tr><td>{ 1, 1, 1, 1, 1 }</td><td>1</td><td>5</td><td>−4</td></tr></tbody></table> <h2 id="notations">Notations</h2> <p>The following notations are used to specify how many partitions have a given rank. Let <i>n</i>, <i>q</i> be a positive integers and <i>m</i> be any integer. </p> <ul><li>The total number of partitions of <i>n</i> is denoted by <i>p</i>(<i>n</i>).</li> <li>The number of partitions of <i>n</i> with rank <i>m</i> is denoted by <i>N</i>(<i>m</i>, <i>n</i>).</li> <li>The number of partitions of <i>n</i> with rank congruent to <i>m</i> modulo <i>q</i> is denoted by <i>N</i>(<i>m</i>, <i>q</i>, <i>n</i>).</li> <li>The number of strict partitions of <i>n</i> is denoted by <i>Q</i>(<i>n</i>).</li> <li>The number of strict partitions of <i>n</i> with rank <i>m</i> is denoted by <i>R</i>(<i>m</i>, <i>n</i>).</li> <li>The number of strict partitions of <i>n</i> with rank congruent to <i>m</i> modulo <i>q</i> is denoted by <i>T</i>(<i>m</i>, <i>q</i>, <i>n</i>).</li></ul> <p>For example, </p> <i>p</i>(5) = 7 , <i>N</i>(2, 5) = 1 , <i>N</i>(3, 5) = 0 , <i>N</i>(2, 2, 5) = 5 . <i>Q</i>(5) = 3 , <i>R</i>(2, 5) = 1 , <i>R</i>(3, 5) = 0 , <i>T</i>(2, 2, 5) = 2. <h2 id="some-basic-results">Some basic results</h2> <p>Let <i>n</i>, <i>q</i> be a positive integers and <i>m</i> be any integer.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> <ul><li> N ( m , n ) = N ( − m , n ) {\displaystyle N(m,n)=N(-m,n)} </li> <li> N ( m , q , n ) = N ( q − m , q , n ) {\displaystyle N(m,q,n)=N(q-m,q,n)} </li> <li> N ( m , q , n ) = ∑ r = − ∞ ∞ N ( m + r q , n ) {\displaystyle N(m,q,n)=\sum _{r=-\infty }^{\infty }N(m+rq,n)} </li></ul> <h2 id="ramanujans-congruences-and-dysons-conjecture">Ramanujan's congruences and Dyson's conjecture</h2> <p>Srinivasa Ramanujan in a paper published in 1919 proved the following <a href="/facts/Ramanujan%27s_congruences/HhcD7AFu">congruences</a> involving the partition function <i>p</i>(<i>n</i>):<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p> <ul><li><i>p</i>(5<i>n</i> + 4) ≡ 0 (mod 5)</li> <li><i>p</i>(7<i>n</i> + 5) ≡ 0 (mod 7)</li> <li><i>p</i>(11<i>n</i> + 6) ≡ 0 (mod 11)</li></ul> <p>In commenting on this result, Dyson noted that " . . . although we can prove that the partitions of 5<i>n</i> + 4 can be divided into five equally numerous subclasses, it is unsatisfactory to receive from the proofs no concrete idea of how the division is to be made. We require a proof which will not appeal to generating functions, . . . ".<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> Dyson introduced the idea of rank of a partition to accomplish the task he set for himself. Using this new idea, he made the following conjectures: </p> <ul><li><i>N</i>(0, 5, 5<i>n</i> + 4) = <i>N</i>(1, 5, 5<i>n</i> + 4) = <i>N</i>(2, 5, 5<i>n</i> + 4) = <i>N</i>(3, 5, 5<i>n</i> + 4) = <i>N</i>(4, 5, 5<i>n</i> + 4)</li> <li><i>N</i>(0, 7, 7<i>n</i> + 5) = <i>N</i>(1, 7, 7<i>n</i> + 5) = <i>N</i>(2, 7, 7<i>n</i> + 5) = . . . = <i>N</i>(6, 7, 7<i>n</i> + 5)</li></ul> <p>These conjectures were proved by Atkin and Swinnerton-Dyer in 1954.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p><p>The following tables show how the partitions of the integers 4 (5 × <i>n</i> + 4 with <i>n</i> = 0) and 9 (5 × <i>n</i> + 4 with <i>n</i> = 1 ) get divided into five equally numerous subclasses. </p> <p>Partitions of the integer 4 </p> <table><tbody><tr><th>Partitions with rank ≡ 0 (mod 5)</th><th>Partitions with rank ≡ 1 (mod 5)</th><th>Partitions with rank ≡ 2 (mod 5)</th><th>Partitions with rank ≡ 3 (mod 5)</th><th>Partitions with rank ≡ 4 (mod 5)</th></tr><tr><td>{ 2, 2 }</td><td>{ 3, 1 }</td><td>{ 1, 1, 1, 1 }</td><td>{ 4 }</td><td>{ 2, 1, 1 }</td></tr></tbody></table> <p>Partitions of the integer 9 </p> <table><tbody><tr><th>Partitions with rank ≡ 0 (mod 5)</th><th>Partitions with rank ≡ 1 (mod 5)</th><th>Partitions with rank ≡ 2 (mod 5)</th><th>Partitions with rank ≡ 3 (mod 5)</th><th>Partitions with rank ≡ 4 (mod 5)</th></tr><tr><td>{ 7, 2 }</td><td>{ 8, 1 }</td><td>{ 6, 1, 1, 1 }</td><td>{ 9 }</td><td>{ 7, 1, 1 }</td></tr><tr><td>{ 5, 1, 1, 1, 1 }</td><td>{ 5, 2, 1, 1 }</td><td>{ 5, 3, 1}</td><td>{ 6, 2, 1 }</td><td>{ 6, 3 }</td></tr><tr><td>{ 4, 3, 1, 1 }</td><td>{ 4, 4, 1 }</td><td>{ 5, 2, 2 }</td><td>{ 5, 4 }</td><td>{ 4, 2, 1, 1, 1 }</td></tr><tr><td>{ 4, 2, 2, 1 }</td><td>{ 4, 3, 2 }</td><td>{ 3, 2, 1, 1, 1, 1 }</td><td>{ 3, 3, 1, 1, 1 }</td><td>{ 3, 3, 2, 1 }</td></tr><tr><td>{ 3, 3, 3 }</td><td>{ 3, 1, 1, 1, 1, 1, 1 }</td><td>{ 2, 2, 2, 2, 1 }</td><td>{ 4, 1, 1, 1, 1, 1 }</td><td>{ 3, 2, 2, 2 }</td></tr><tr><td>{ 2, 2, 1, 1, 1, 1, 1 }</td><td>{ 2, 2, 2, 1, 1, 1 }</td><td>{ 1, 1, 1, 1, 1, 1, 1, 1, 1 }</td><td>{ 3, 2, 2, 1, 1}</td><td>{ 2, 1, 1, 1, 1, 1, 1, 1 }</td></tr></tbody></table> <h2 id="generating-functions">Generating functions</h2> <ul><li>The generating function of <i>p</i>(<i>n</i>) was discovered by Euler and is well known.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a></li></ul> ∑ n = 0 ∞ p ( n ) x n = ∏ k = 1 ∞ 1 1 − x k {\displaystyle \sum _{n=0}^{\infty }p(n)x^{n}=\prod _{k=1}^{\infty }{\frac {1}{1-x^{k}}}} <ul><li>The generating function for <i>N</i>(<i>m</i>, <i>n</i>) is given below:<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a></li></ul> ∑ m = − ∞ ∞ ∑ n = 0 ∞ N ( m , n ) z m q n = 1 + ∑ n = 1 ∞ q n 2 ∏ k = 1 n ( 1 − z q k ) ( 1 − z − 1 q k ) {\displaystyle \sum _{m=-\infty }^{\infty }\sum _{n=0}^{\infty }N(m,n)z^{m}q^{n}=1+\sum _{n=1}^{\infty }{\frac {q^{n^{2}}}{\prod _{k=1}^{n}(1-zq^{k})(1-z^{-1}q^{k})}}} <ul><li>The generating function for <i>Q</i>(<i>n</i>) is given below:<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a></li></ul> ∑ n = 0 ∞ Q ( n ) x n = ∏ k = 0 ∞ 1 1 − x 2 k − 1 {\displaystyle \sum _{n=0}^{\infty }Q(n)x^{n}=\prod _{k=0}^{\infty }{\frac {1}{1-x^{2k-1}}}} <ul><li>The generating function for <i>R</i>(<i>m</i>, <i>n</i>) is given below:<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li></ul> ∑ m , n = 0 ∞ R ( m , n ) z m q n = 1 + ∑ s = 1 ∞ q s ( s + 1 ) / 2 ( 1 − z q ) ( 1 − z q 2 ) ⋯ ( 1 − z q s ) {\displaystyle \sum _{m,n=0}^{\infty }R(m,n)z^{m}q^{n}=1+\sum _{s=1}^{\infty }{\frac {q^{s(s+1)/2}}{(1-zq)(1-zq^{2})\cdots (1-zq^{s})}}} <h2 id="alternate-definition">Alternate definition</h2> <p class="note">Main article: <a href="/facts/Durfee_square/BdebsgX3">Durfee square</a></p> <p>In combinatorics, the phrase <i>rank of a partition</i> is sometimes used to describe a different concept: the rank of a partition λ is the largest integer <i>i</i> such that λ has at least <i>i</i> parts each of which is no smaller than <i>i</i>.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> Equivalently, this is the length of the main diagonal in the <a href="/facts/Young_diagram/e5lI4bck">Young diagram</a> or <a href="/facts/Ferrers_diagram/LtyXWqwH">Ferrers diagram</a> for λ, or the side-length of the <a href="/facts/Durfee_square/BdebsgX3">Durfee square</a> of λ. </p><p>The table of ranks (under this alternate definition) of partitions of 5 is given below. </p> <p>Ranks of the partitions of the integer 5 </p> <table><tbody><tr><th>Partition</th><th>Rank</th></tr><tr><td>{ 5 }</td><td>1</td></tr><tr><td>{ 4, 1 }</td><td>1</td></tr><tr><td>{ 3, 2 }</td><td>2</td></tr><tr><td>{ 3, 1, 1 }</td><td>1</td></tr><tr><td>{ 2, 2, 1 }</td><td>2</td></tr><tr><td>{ 2, 1, 1, 1 }</td><td>1</td></tr><tr><td>{ 1, 1, 1, 1, 1 }</td><td>1</td></tr></tbody></table> <h2 id="further-reading">Further reading</h2> <ul><li>Asymptotic formulas for the rank partition function:<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></li> <li>Congruences for rank function:<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a></li> <li>Generalisation of rank to BG-rank:<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a></li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Crank_of_a_partition/BFl4GazU">Crank of a partition</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>F. Dyson (1944). "Some guesses in the theory of partitions" (PDF). Eureka (Cambridge). 8: 10–15. <a href="https://www.archim.org.uk/eureka/archive/Eureka-8.pdf" target="_blank">https://www.archim.org.uk/eureka/archive/Eureka-8.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>F. Dyson (1944). "Some guesses in the theory of partitions" (PDF). Eureka (Cambridge). 8: 10–15. <a href="https://www.archim.org.uk/eureka/archive/Eureka-8.pdf" target="_blank">https://www.archim.org.uk/eureka/archive/Eureka-8.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>F. Dyson (1944). "Some guesses in the theory of partitions" (PDF). Eureka (Cambridge). 8: 10–15. <a href="https://www.archim.org.uk/eureka/archive/Eureka-8.pdf" target="_blank">https://www.archim.org.uk/eureka/archive/Eureka-8.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>F. Dyson (1944). "Some guesses in the theory of partitions" (PDF). Eureka (Cambridge). 8: 10–15. <a href="https://www.archim.org.uk/eureka/archive/Eureka-8.pdf" target="_blank">https://www.archim.org.uk/eureka/archive/Eureka-8.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Srinivasa, Ramanujan (1919). "Some properties of p(n), number of partitions of n". Proceedings of the Cambridge Philosophical Society. XIX: 207–210. <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>F. Dyson (1944). "Some guesses in the theory of partitions" (PDF). Eureka (Cambridge). 8: 10–15. <a href="https://www.archim.org.uk/eureka/archive/Eureka-8.pdf" target="_blank">https://www.archim.org.uk/eureka/archive/Eureka-8.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>A. O. L. Atkin; H. P. F. Swinnerton-Dyer (1954). "Some properties of partitions". Proceedings of the London Mathematical Society. 66 (4): 84–106. doi:10.1112/plms/s3-4.1.84. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>G.H. Hardy and E.W. Wright (1938). An introduction to the theory of numbers. London: Oxford University Press. p. 274. <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Bringmann, Kathrin (2009). "Congruences for Dyson's ranks" (PDF). International Journal of Number Theory. 5 (4): 573–584. doi:10.1142/S1793042109002262. Retrieved 24 November 2012. <a href="http://www.mi.uni-koeln.de/Bringmann/rankcong.pdf" target="_blank">http://www.mi.uni-koeln.de/Bringmann/rankcong.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Maria Monks (2010). "Number theoretic properties of generating functions related to Dyson's rank for partitions into distinct parts" (PDF). Proceedings of the American Mathematical Society. 138 (2): 481–494. doi:10.1090/s0002-9939-09-10076-x. Retrieved 24 November 2012. <a href="http://www.math.wisc.edu/~ono/reu08monks.pdf" target="_blank">http://www.math.wisc.edu/~ono/reu08monks.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Maria Monks (2010). "Number theoretic properties of generating functions related to Dyson's rank for partitions into distinct parts" (PDF). Proceedings of the American Mathematical Society. 138 (2): 481–494. doi:10.1090/s0002-9939-09-10076-x. Retrieved 24 November 2012. <a href="http://www.math.wisc.edu/~ono/reu08monks.pdf" target="_blank">http://www.math.wisc.edu/~ono/reu08monks.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Stanley, Richard P. (1999) Enumerative Combinatorics, Volume 2, p. 289. Cambridge University Press. ISBN 0-521-56069-1. <a href="/wiki/Richard_P._Stanley" target="_blank">/wiki/Richard_P._Stanley</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Bringman, Kathrin (July 2009). "Asymptotics For Rank Partition Functions" (PDF). Transactions of the American Mathematical Society. 361 (7): 3483–3500. arXiv:0708.0691. doi:10.1090/s0002-9947-09-04553-x. S2CID 42465633. Retrieved 21 November 2012. <a href="https://www.ams.org/journals/tran/2009-361-07/S0002-9947-09-04553-X/S0002-9947-09-04553-X.pdf" target="_blank">https://www.ams.org/journals/tran/2009-361-07/S0002-9947-09-04553-X/S0002-9947-09-04553-X.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Bringmann, Kathrin (2009). "Congruences for Dyson's rank" (PDF). International Journal of Number Theory. 5 (4): 573–584. doi:10.1142/S1793042109002262. Retrieved 21 November 2012. <a href="http://www.mi.uni-koeln.de/Bringmann/rankcong.pdf" target="_blank">http://www.mi.uni-koeln.de/Bringmann/rankcong.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Berkovich, Alexander; Garvan, Frank G. (2008). "The BG-rank of a partition and its applications" (PDF). Advances in Applied Mathematics. 40 (3): 377–400. arXiv:math/0602362. doi:10.1016/j.aam.2007.04.002. S2CID 7337479. Retrieved 21 November 2012. <a href="http://www.math.ufl.edu/~fgarvan/papers/bgrank.pdf" target="_blank">http://www.math.ufl.edu/~fgarvan/papers/bgrank.pdf</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> </ol>