Editing Integer partition (section)

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