 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 Andrews (1976), which are additive partitions 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 Hughes & Shallit (1983). The Latin name "factorisatio numerorum" had been used previously. MathWorld uses the name unordered factorization.
Contents
Examples
 The number 20 has four multiplicative partitions: 2 × 2 × 5, 2 × 10, 4 × 5, and 20.
 3 × 3 × 3 × 3, 3 × 3 × 9, 3 × 27, 9 × 9, and 81 are the five multiplicative permutations of 81 = 3^{4}. Because it is the fourth power of a prime, 81 has the same number (five) of multiplicative partitions as 4 does of additive partitions.
 The number 30 has five multiplicative partitions: 2 × 3 × 5 = 2 × 15 = 6 × 5 = 3 × 10 = 30.
 In general, the number of multiplicative partitions of a squarefree number with i distinct prime factors is the ith Bell number , B_{i}.
Application
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^{11}, p×q^{5}, p^{2}×q^{3}, and p×q×r^{2}, where p, q, and r are distinct prime numbers; these forms correspond to the multiplicative partitions 12, 2×6, 3×4, and 2×2×3 respectively. More generally, for each multiplicative partition
of the integer k, there corresponds a class of integers having exactly k divisors, of the form
where each p_{i} is a distinct prime. This correspondence follows from the multiplicative property of the divisor function.
Bounds on the number of partitions
Oppenheim (1926) credits 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_{n}, McMahon and Oppenheim observed that its Dirichlet series generating function ƒ(s) has the product representation
The sequence of numbers a_{n} begins
Oppenheim also claimed an upper bound on a_{n}, of the form
but as Canfield, Erdős & Pomerance (1983) showed, this bound is erroneous and the true bound is
Both of these bounds are not far from linear in n: they are of the form n^{1−o(1)}. However, the typical value of a_{n} is much smaller: the average value of a_{n}, averaged over an interval x ≤ n ≤ x+N, is
a bound that is of the form n^{o(1)} (Luca, Mukhopadhyay & Srinivas 2008).
Additional results
Canfield, Erdős & Pomerance (1983) observe, and Luca, Mukhopadhyay & Srinivas (2008) prove, that most numbers cannot arise as the number a_{n} of multiplicative partitions of some n: the number of values less than N which arise in this way is N^{O(log log log N / log log N)}. Additionally, Luca, Mukhopadhyay & Srinivas (2008) show that most values of n are not multiples of a_{n}: the number of values n ≤ N such that a_{n} divides n is O(N / log^{1 + o(1)} N).
See also
References
 Andrews, G. (1976), The Theory of Partitions, AddisonWesley, chapter 12.
 Canfield, E. R.; Erdős, Paul; Pomerance, Carl (1983), "On a problem of Oppenheim concerning "factorisatio numerorum"", Journal of Number Theory 17 (1): 1–28, doi:10.1016/0022314X(83)900021.
 Hughes, John F.; Shallit, Jeffrey (1983), "On the number of multiplicative partitions", American Mathematical Monthly 90 (7): 468–471, doi:10.2307/2975729, JSTOR 2975729.
 Knopfmacher, A.; Mays, M. (2006), "Ordered and Unordered Factorizations of Integers", Mathematica Journal 10: 72–89. As cited by MathWorld.
 Luca, Florian; Mukhopadhyay, Anirban; Srinivas, Kotyada (2008), On the Oppenheim's "factorisatio numerorum" function, arXiv:0807.0986.
 MacMahon, P. A. (1923), "Dirichlet series and the theory of partitions", Proceedings of the London Mathematical Society 22: 404–411, doi:10.1112/plms/s222.1.404, http://plms.oxfordjournals.org/cgi/reprint/s222/1/404.
 Oppenheim, A. (1926), "On an arithmetic function", Journal of the London Mathematical Society 1 (4): 205–211, doi:10.1112/jlms/s11.4.205, http://jlms.oxfordjournals.org/cgi/reprint/s11/4/205.
Further reading
 Knopfmacher, A.; Mays, M. E. (2005), "A survey of factorization counting functions", International Journal of Number Theory 1 (4): 563–581, doi:10.1142/S1793042105000315, http://math.wvu.edu/~mays/Papers/apf7.pdf
External links
Categories: Number theory
 Integer sequences
Wikimedia Foundation. 2010.
Look at other dictionaries:
Multiplicative — may refer to: Multiplication Multiplicative partition A Multiplicative function For the Multiplicative numerals, once, twice, and thrice, see English numerals This disambiguation page lists articles associated with the same title. If an … Wikipedia
Partition (number theory) — Young diagrams associated to the partitions of the positive integers 1 through 8. They are so arranged that images under the reflection about the main diagonal of the square are conjugate partitions. In number theory and combinatorics, a… … Wikipedia
Partition — Generally, a partition is a splitting of something into parts. The term is used in a variety of senses: Law *Partition (law), to divide up a piece of land into separate portions representing the proportionate interests of the tenants. It may also … Wikipedia
List of partition topics — This is a list of partition topics, in the mathematical sense. Partition (disambiguation) lists meanings in other fields. In mathematics, a partition may be a partition of a set or an ordered partition of a set, or a partition of a graph, or a… … Wikipedia
Plane partition — In mathematics, a plane partition (also solid partition) is a two dimensional array of nonnegative integers n {i,j} which are nonincreasing from left to right and top to bottom:: n {i,j} ge n {i,j+1} quadmbox{and}quad n {i,j} ge n {i+1,j} , .… … Wikipedia
List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… … Wikipedia
Arithmetic function — In number theory, an arithmetic (or arithmetical) function is a real or complex valued function ƒ(n) defined on the set of natural numbers (i.e. positive integers) that expresses some arithmetical property of n. [1] An example of an arithmetic… … Wikipedia
Ising model — The Ising model, named after the physicist Ernst Ising, is a mathematical model in statistical mechanics. It has since been used to model diverse phenomena in which bits of information, interacting in pairs, produce collectiveeffects.Definition… … Wikipedia
Quotient group — In mathematics, given a group G and a normal subgroup N of G , the quotient group, or factor group, of G over N is intuitively a group that collapses the normal subgroup N to the identity element. The quotient group is written G / N and is… … Wikipedia
Group (mathematics) — This article covers basic notions. For advanced topics, see Group theory. The possible manipulations of this Rubik s Cube form a group. In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines … Wikipedia