Content deleted Content added
Undid revision 1131177993 by LaplaceFox (talk) there is nothing wrong with the previous form |
→Strict partition function: general restricted partition function and asymptotic growth rate (moved here from article on partitions) |
||
Line 235:
: <math>= P(4)Q(1) + P(3)Q(3) + P(2)Q(5) + P(1)Q(7) + P(0)Q(9) = </math>
: <math>= 5\times 1 + 3\times 2 + 2\times 3 + 1\times 5 + 1\times 8 = 30 </math>
== Restricted partition function ==
More generally, if ''A'' is a set of natural numbers, we can consider partitions restricted to only elements in ''A''. The restricted partition function is then denoted ''p''<sub>''A''</sub>(''n''), or ''p''(''A'', ''n'').
Some general results on the asymptotic properties of the restricted partition function are known. If ''A'' possesses positive [[natural density]] α then
:<math> \log p_A(n) \sim C \sqrt{\alpha n} </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>{{cite journal | zbl=0061.07905 | last=Erdős | first=Pál | author-link=Paul Erdős | title=On an elementary proof of some asymptotic formulas in the theory of partitions | journal=Ann. Math. | series=(2) | volume=43 | pages=437–450 | year=1942 | issue=3 | doi=10.2307/1968802| jstor=1968802 }}</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==
| |||