Editing Integer partition (section)

==Restricted partitions==
In both combinatorics and number theory, families of partitions subject to various restrictions are often studied.<ref>{{cite journal|last=Alder|first=Henry L.|title=Partition identities - from Euler to the present|journal=American Mathematical Monthly|volume=76|year=1969|issue=7|pages=733–746|url=http://www.maa.org/programs/maa-awards/writing-awards/partition-identities-from-euler-to-the-present|doi=10.2307/2317861|jstor=2317861}}</ref>  This section surveys a few such restrictions.

===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:

{|
|- style="vertical-align:top; text-align:left;"
| [[File:RedDot.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:RedDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:RedDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]
| style="vertical-align:middle;"| ↔
| [[File:RedDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:RedDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]
|- style="vertical-align:top; text-align:center;"
| 6 + 4 + 3 + 1
| =
| 4 + 3 + 3 + 2 + 1 + 1
|}

By turning the rows into columns, we obtain the partition 4&nbsp;+&nbsp;3&nbsp;+&nbsp;3&nbsp;+&nbsp;2&nbsp;+&nbsp;1&nbsp;+&nbsp;1 of the number 14. Such partitions are said to be ''conjugate'' of one another.{{sfn|Hardy|Wright|2008|p=362}} In the case of the number 4, partitions 4 and 1&nbsp;+&nbsp;1&nbsp;+&nbsp;1&nbsp;+&nbsp;1 are conjugate pairs, and partitions 3&nbsp;+&nbsp;1 and 2&nbsp;+&nbsp;1&nbsp;+&nbsp;1 are conjugate of each other. Of particular interest are partitions, such as 2&nbsp;+&nbsp;2, which have themselves as conjugate. Such partitions are said to be ''self-conjugate''.{{sfn|Hardy|Wright|2008|p=368}}

'''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:

{|
|-
| style="vertical-align:top;"| [[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]
| style="vertical-align:top;"| &nbsp; ↔ &nbsp;
| style="vertical-align:top;"| [[File:RedDot.svg|16px|*]][[File:GrayDot.svg|16px|*]][[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|*]]
|}

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:

{|
|-
| valign="top" | 
[[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]]
<br />
[[File:RedDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:RedDot.svg|16px|*]]
<br />
[[File:BlackDot.svg|16px|x]][[File:BlackDot.svg|16px|x]][[File:BlackDot.svg|16px|x]]
| style="vertical-align:middle;"| ↔
| valign="top" | [[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]][[File:GrayDot.svg|16px|o]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:RedDot.svg|16px|*]][[File:RedDot.svg|16px|*]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]][[File:BlackDot.svg|16px|x]][[File:BlackDot.svg|16px|x]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]][[File:BlackDot.svg|16px|x]]<br />[[File:GrayDot.svg|16px|o]][[File:RedDot.svg|16px|*]]
|- style="vertical-align:top; text-align:center;"
| 9 + 7 + 3
| =
| 5 + 5 + 4 + 3 + 2
|- style="vertical-align:top; text-align:center;"
| Dist. odd
|
| self-conjugate
|}

===Odd parts and distinct parts {{anchor|Euler's partition theorem}}===
Among the 22 partitions of the number 8, there are 6 that contain only ''odd parts'':
* 7 + 1
* 5 + 3
* 5 + 1 + 1 + 1
* 3 + 3 + 1 + 1
* 3 + 1 + 1 + 1 + 1 + 1
* 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

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:
* 8
* 7 + 1 
* 6 + 2
* 5 + 3
* 5 + 2 + 1
* 4 + 3 + 1

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'').{{sfn|Hardy|Wright|2008|p=365}}<ref>Notation follows {{harvnb|Abramowitz| Stegun|1964|p=825}}</ref> This result was proved by [[Leonhard Euler]] in 1748<ref>{{cite book|author-link=George Andrews (mathematician)|last=Andrews|first=George E.|title=Number Theory|publisher=W. B. Saunders Company|location=Philadelphia|date=1971|pages= 149–50}}</ref> and later was generalized as [[Glaisher's theorem]].

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, ... {{OEIS|id=A000009}}.

The [[generating function]] for ''q''(''n'') is given by<ref>{{harvnb|Abramowitz|Stegun|1964|p=825}}, 24.2.2 eq. I(B)</ref> 
:<math>\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}} .</math>

The [[pentagonal number theorem]] gives a recurrence for ''q'':<ref>{{harvnb|Abramowitz|Stegun|1964|p=826}}, 24.2.2 eq. II(A)</ref> 
:''q''(''k'') = ''a''<sub>''k''</sub> + ''q''(''k'' &minus; 1) + ''q''(''k'' &minus; 2) &minus; ''q''(''k'' &minus; 5) &minus; ''q''(''k'' &minus; 7) + ''q''(''k'' &minus; 12) + ''q''(''k'' &minus; 15) &minus; ''q''(''k'' &minus; 22) &minus; ...
where ''a''<sub>''k''</sub> is (&minus;1)<sup>''m''</sup> if ''k'' = 3''m''<sup>2</sup> &minus; ''m'' for some integer ''m'' and is 0 otherwise.

===Restricted part size or number of parts===
{{main|Triangle of partition numbers}}
By taking conjugates, the number {{math|''p''<sub>''k''</sub>(''n'')}} of partitions of {{math|''n''}} into exactly ''k'' parts is equal to the number of partitions of {{math|''n''}} in which the largest part has size {{math|''k''}}.  The function {{math|''p''<sub>''k''</sub>(''n'')}} satisfies the recurrence
: {{math|1=''p''<sub>''k''</sub>(''n'') = ''p''<sub>''k''</sub>(''n'' − ''k'') + ''p''<sub>''k''−1</sub>(''n'' &minus; 1)}}
with initial values {{math|1=''p''<sub>0</sub>(0) = 1}} and {{math|1=''p''<sub>''k''</sub>(''n'') = 0}} if {{math|''n'' &le; 0 or ''k'' &le; 0}} and {{math|''n''}} and {{math|''k''}} are not both zero.<ref>Richard Stanley, ''Enumerative Combinatorics'', volume 1, second edition.  Cambridge University Press, 2012.  Chapter 1, section 1.7.</ref>

One recovers the function ''p''(''n'') by

:<math>
p(n) = \sum_{k = 0}^n p_k(n).
</math>

One possible generating function for such partitions, taking ''k'' fixed and ''n'' variable, is 
: <math> \sum_{n \geq 0} p_k(n) x^n = x^k\prod_{i = 1}^k \frac{1}{1 - x^i}.</math>

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 [[generating function]] 
:<math>\prod_{t \in T}(1-x^t)^{-1}.</math>
This can be used to solve [[change-making problem]]s (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
:<math>\left \lfloor \frac{n}{2}+1 \right \rfloor ,</math>
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)<sup>2</sup> / 12.<ref>{{cite book|last=Hardy|first=G.H.|title=Some Famous Problems of the Theory of Numbers|url=https://archive.org/details/in.ernet.dli.2015.84630|publisher=Clarendon Press|date=1920}}</ref>

===Partitions in a rectangle and Gaussian binomial coefficients===
{{Main|Gaussian binomial coefficient}}
One may also simultaneously limit the number and size of the parts.  Let {{math|''p''(''N'', ''M''; ''n'')}} denote the number of partitions of {{mvar|n}} with at most {{mvar|M}} parts, each of size at most {{mvar|N}}.  Equivalently, these are the partitions whose Young diagram fits inside an {{math|''M'' × ''N''}} rectangle.  There is a recurrence relation
<math display=block>p(N,M;n) = p(N,M-1;n) + p(N-1,M;n-M)</math>
obtained by observing that <math>p(N,M;n) - p(N,M-1;n)</math> counts the partitions of {{mvar|n}} into exactly {{mvar|M}} parts of size at most {{mvar|N}}, and subtracting 1 from each part of such a partition yields a partition of {{math|''n'' − ''M''}} into at most {{mvar|M}} parts.{{sfn|Andrews|1976|pp=33–34}}

The Gaussian binomial coefficient is defined as:
<math display=block>{k+\ell \choose \ell}_q = {k+\ell \choose k}_q = \frac{\prod^{k+\ell}_{j=1}(1-q^j)}{\prod^{k}_{j=1}(1-q^j)\prod^{\ell}_{j=1}(1-q^j)}.</math>
The Gaussian binomial coefficient is related to the [[generating function]] of {{math|''p''(''N'', ''M''; ''n'')}} by the equality
<math display=block>\sum^{MN}_{n=0}p(N,M;n)q^n = {M+N \choose M}_q.</math>