Partition function (number theory): Difference between revisions

Revision as of 16:15, 18 January 2023

Revision as of 09:19, 19 January 2023

Line 238:

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

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''_''A''(''n''), or ''p''(''A'', ''n'').

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

=== 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|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''_''A''(''n'') possessesis positivethe [[naturalpartition density]]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>

with <math>C = \pi\sqrt\frac23</math>

and conversely if this asymptotic property holds for ''p''_''A''(''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}}