View source for Multiplicative partition

In [[number theory]], a '''multiplicative partition''' or '''unordered factorization''' of an integer ''n'' that is greater than 1 is a way of writing ''n'' as a product of integers greater than 1, treating two products as equivalent if they differ only in the ordering of the factors. The number ''n'' is itself considered one of these products. Multiplicative partitions closely parallel the study of '''multipartite partitions''', discussed in {{harvtxt|Andrews|1976}}, which are additive [[partition]]s of finite sequences of positive integers, with the addition made [[pointwise]]. Although the study of multiplicative partitions has been ongoing since at least 1923, the name "multiplicative partition" appears to have been introduced by {{harvtxt|Hughes|Shallit|1983}}. The Latin name "factorisatio numerorum" had been used previously.  [[MathWorld]] uses the name '''unordered factorization'''.

==Examples==
*The number 20 has four multiplicative partitions: 2&nbsp;&times;&nbsp;2&nbsp;&times;&nbsp;5, 2&nbsp;&times;&nbsp;10, 4&nbsp;&times;&nbsp;5, and 20. 
*3&nbsp;&times;&nbsp;3&nbsp;&times;&nbsp;3&nbsp;&times;&nbsp;3, 3&nbsp;&times;&nbsp;3&nbsp;&times;&nbsp;9, 3&nbsp;&times;&nbsp;27, 9&nbsp;&times;&nbsp;9, and 81 are the five multiplicative permutations of 81 = 3<sup>4</sup>. Because it is the fourth power of a [[prime number|prime]], 81 has the same number (five) of multiplicative partitions as 4 does of [[partition (number theory)|additive partitions]].
*The number 30 has five multiplicative partitions: 2&nbsp;&times;&nbsp;3&nbsp;&times;&nbsp;5 = 2&nbsp;&times;&nbsp;15 = 6&nbsp;&times;&nbsp;5 = 3&nbsp;&times;&nbsp;10 = 30.
*In general, the number of multiplicative partitions of a [[Square-free integer|squarefree]] number with '''i''' distinct prime factors is the ith [[Bell number]] , B<sub>i</sub>.

==Application==
{{harvtxt|Hughes|Shallit|1983}} describe an application of multiplicative partitions in classifying integers with a given number of divisors. For example, the integers with exactly 12 divisors take the forms ''p''<sup>11</sup>, ''p''&times;''q''<sup>5</sup>, ''p''<sup>2</sup>&times;''q''<sup>3</sup>, and ''p''&times;''q''&times;''r''<sup>2</sup>, where ''p'', ''q'', and ''r'' are distinct [[prime number]]s; these forms correspond to the multiplicative partitions 12, 2&times;6, 3&times;4, and 2&times;2&times;3 respectively. More generally, for each multiplicative partition
:<math>k = \prod t_i</math>
of the integer ''k'', there corresponds a class of integers having exactly ''k'' divisors, of the form
:<math>\prod p_i^{t_i-1},</math>
where each ''p''<sub>''i''</sub> is a distinct prime. This correspondence follows from the [[Multiplicative function|multiplicative]] property of the [[divisor function]].

==Bounds on the number of partitions==
{{harvtxt|Oppenheim|1926}} credits {{harvtxt|McMahon|1923}} with the problem of counting the number of multiplicative partitions of ''n''; this problem has since been studied by other others under the Latin name of ''factorisatio numerorum''. If the number of multiplicative partitions of ''n'' is ''a''<sub>''n''</sub>, McMahon and Oppenheim observed that its [[Dirichlet series]] generating function &fnof;(''s'') has the product representation

:<math>f(s)=\sum_{n=1}^{\infty}\frac{a_n}{n^s}=\prod_{k=2}^{\infty}\frac{1}{1-k^{-s}}.</math>

The sequence of numbers ''a<sub>n</sub>'' begins

:1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 4, 1, 2, 2, 5, ... {{OEIS|id=A001055}}.

Oppenheim also claimed an upper bound on ''a<sub>n</sub>'', of the form
:<math>a_n\le n\left(\exp\frac{\log n\log\log\log n}{\log\log n}\right)^{-2+o(1)},</math>
but as {{harvtxt|Canfield|Erdős|Pomerance|1983}} showed, this bound is erroneous and the true bound is

:<math>a_n\le n\left(\exp\frac{\log n\log\log\log n}{\log\log n}\right)^{-1+o(1)}.</math>

Both of these bounds are not far from linear in ''n'': they are of the form ''n''<sup>1&minus;o(1)</sup>.
However, the typical value of ''a<sub>n</sub>'' is much smaller: the average value of ''a<sub>n</sub>'', averaged over an interval ''x''&nbsp;≤&nbsp;''n''&nbsp;≤&nbsp;''x''+''N'', is
:<math>\bar a = \exp\left(\frac{4\sqrt{\log N}}{\sqrt{2e}\log\log N}\bigl(1+o(1)\bigr)\right),</math>
a bound that is of the form ''n''<sup>o(1)</sup> {{harv|Luca|Mukhopadhyay|Srinivas|2008}}.

==Additional results==
{{harvtxt|Canfield|Erdős|Pomerance|1983}} observe, and {{harvtxt|Luca|Mukhopadhyay|Srinivas|2008}} prove, that most numbers cannot arise as the number ''a<sub>n</sub>'' of multiplicative partitions of some ''n'': the number of values less than ''N'' which arise in this way is ''N''<sup>O(log&nbsp;log&nbsp;log&nbsp;''N''&nbsp;/&nbsp;log&nbsp;log&nbsp;''N'')</sup>. Additionally, {{harvtxt|Luca|Mukhopadhyay|Srinivas|2008}} show that most values of ''n'' are not multiples of ''a<sub>n</sub>'': the number of values ''n'' ≤ ''N'' such that ''a<sub>n</sub>'' divides ''n'' is O(''N''&nbsp;/&nbsp;log<sup>1&nbsp;+&nbsp;o(1)</sup>&nbsp;''N'').

==See also==

*[[partition (number theory)]]
*[[divisor]]

==References==
*{{citation|first=G.|last=Andrews|authorlink=George E. Andrews|title=The Theory of Partitions|year=1976|publisher=Addison-Wesley}}, chapter 12.
*{{citation|doi=10.1016/0022-314X(83)90002-1|first1=E. R.|last1=Canfield|first2=Paul|last2=Erdős|authorlink2=Paul Erdős|first3=Carl|last3=Pomerance|authorlink3=Carl Pomerance|title=On a problem of Oppenheim concerning "factorisatio numerorum"|journal=[[Journal of Number Theory]]|volume=17|year=1983|issue=1|pages=1–28}}.
*{{citation|first1=John F.|last1=Hughes|first2=Jeffrey|last2=Shallit|authorlink2=Jeffrey Shallit|title=On the number of multiplicative partitions|url=http://jstor.org/stable/2975729|journal=[[American Mathematical Monthly]]|year=1983|volume=90|issue=7|pages=468–471|doi=10.2307/2975729}}.
*{{citation|first1=A.|last1=Knopfmacher|first2=M.|last2=Mays|title=Ordered and Unordered Factorizations of Integers|journal=[[Mathematica Journal]]|volume=10|pages=72–89|year=2006}}. As cited by [[MathWorld]].
*{{citation|first1=Florian|last1=Luca|first2=Anirban|last2=Mukhopadhyay|first3=Kotyada|last3=Srinivas|title=On the Oppenheim's "factorisatio numerorum" function|id={{arxiv|id=0807.0986}}|year=2008}}.
*{{citation|doi=10.1112/plms/s2-22.1.404|first=P. A.|last=MacMahon|authorlink=Percy Alexander MacMahon|title=Dirichlet series and the theory of partitions|journal=[[Proceedings of the London Mathematical Society]]|volume=22|year=1923|pages=404–411|url=http://plms.oxfordjournals.org/cgi/reprint/s2-22/1/404}}.
*{{citation|doi=10.1112/jlms/s1-1.4.205|first=A.|last=Oppenheim|title=On an arithmetic function|journal=[[Journal of the London Mathematical Society]]|volume=1|issue=4|pages=205–211|year=1926|url=http://jlms.oxfordjournals.org/cgi/reprint/s1-1/4/205}}.

==External links==
*{{MathWorld|title=Unordered Factorization|urlname=UnorderedFactorization}}

[[Category:Number theory]]
[[Category:Integer sequences]]