|
: <math>= 5\times 1 + 3\times 2 + 2\times 3 + 1\times 5 + 1\times 8 = 30 </math>
goofy ahh!!
== Restricted partition function ==
More generally, it is possible to consider partitions restricted to only elements of a subset ''A'' of the natural numbers (for example a restriction on the maximum value of the parts), or with a restriction on the number of parts or the maximum difference between parts. Each particular restriction gives rise to an associated partition function with specific properties. Some common examples are given below.
=== Euler and Glaisher's theorem ===
Two important examples are the partitions restricted to only odd integer parts or only even integer parts, with the corresponding partition functions often denoted <math>p_o(n)</math> and <math>p_e(n)</math>.
A theorem from Euler shows that the number of strict partitions is equal to the number of partitions with only odd parts: for all ''n'', <math>q(n) = p_o(n)</math>. This is generalized as [[Glaisher's theorem]], which states that the number of partitions with no more than ''d-1'' repetitions of any part is equal to the number of partitions with no part divisible by ''d''.
=== Gaussian binomial coefficient ===
If we denote <math>p(N, M, n)</math> the number of partitions of ''n'' in at most ''M'' parts, with each part smaller or equal to ''N'', then the generating function of <math>p(N, M, n)</math> is the following [[Gaussian binomial coefficient]]:
:<math>\sum_{n=0}^\infty p(N, M, n)q^n = {N+M \choose M}_q
=
\frac{(1-q^{N+M})(1-q^{N+M-1})\cdots(1-q^{N+1})} {(1-q)(1-q^2)\cdots(1-q^M)}</math>
=== Asymptotics ===
Some general results on the asymptotic properties of restricted partition functions are known. If ''p''<sub>''A''</sub>(''n'') is the partition function of partitions restricted to only elements of a subset ''A'' of the natural numbers, then:
If ''A'' possesses positive [[natural density]] α then <math> \log p_A(n) \sim C \sqrt{\alpha n}</math>, with <math>C = \pi\sqrt\frac23</math>
and conversely if this asymptotic property holds for ''p''<sub>''A''</sub>(''n'') then ''A'' has natural density α.{{sfn|Nathanson|2000|pp=475–85}} This result was stated, with a sketch of proof, by Erdős in 1942.<ref name=erdos42></ref>{{sfn|Nathanson|2000|p=495}}
If ''A'' is a finite set, this analysis does not apply (the density of a finite set is zero). If ''A'' has ''k'' elements whose greatest common divisor is 1, then{{sfn|Nathanson|2000|pp=458–64}}
:<math> p_A(n) = \left(\prod_{a \in A} a^{-1}\right) \cdot \frac{n^{k-1}}{(k-1)!} + O(n^{k-2}) . </math>
==References==
| 