TOPICS
Search

Ordered Factorization

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

An ordered factorization is a factorization (not necessarily into prime factors) in which a×b is considered distinct from b×a. The following table lists the ordered factorizations for the integers 1 through 10.

n#ordered factorizations
111
212
313
422·2, 4
515
632·3, 3·2, 6
717
842·2·2, 2·4, 4·2, 8
923·3, 9
1032·5, 5·2, 10

The numbers of ordered factorizations H(n) of n=1, 2, ... are given by 1, 1, 1, 2, 1, 3, 1, 4, 2, 3, ... (OEIS A074206). This sequence has the Dirichlet generating function

f(s)=1/(2-zeta(s)),
(1)

where zeta(s) is the Riemann zeta function.

A recurrence equation for H(n) is given by

H(n)=sum_(d|n)H(d),
(2)

where the sum is over the divisors of n and H(1)=1 (Hille 1936, Knopfmacher and Mays 2006). Another recurrence also due to Hille (1936) for n>1 is given by

H(n)=2[sum_(p_i)H(n/(p_i))-sum_(p_1,p_2)H(n/(p_ip_j))+...+(-1)^(r-1)H(n/(p_1p_2...p_r))],
(3)

where H(1)=1/2 and

n=p_1^(alpha_1)p_2^(alpha_2)...p_r^(alpha_r)
(4)

is the prime factorization of n (Knopfmacher and Mays 1996).

MacMahon (1893) derived the beautiful double sum formula

H(n)=sum_(j=1)^qsum_(i=0)^(j-1)(-1)^i(j; i)product_(k=1)^r(alpha_k-j-i-1; alpha_k),
(5)

where

q=sum_(k=1)^ralpha_k
(6)

(Knopfmacher and Mays 1996). In the case that n is a product of two prime powers,

n=p_1^(alpha_1)p_2^(alpha_2),
(7)

Chor et al. (2000) showed that

H(n)=2^(alpha_1+alpha_2-1)sum_(k=0)^(alpha_2)(alpha_1; k)(alpha_2; k)2^(-k)
(8)
=2^(alpha_2-1)_2F_1(-alpha_1,alpha_2+1;1;-1),
(9)

where _2F_1(a,b;c;z) is a hypergeometric function.

The number of ordered factorizations of n is equal to the number of perfect partitions of n-1 (Goulden and Jackson 1983, p. 94).

See also

Distinct Prime Factorization, Factorization, Perfect Partition, Prime Factorization, Unordered Factorization

Explore with Wolfram|Alpha

References

Chor, B.; Lemke, P.; and Mador, Z. "On the Number of Ordered Factorizations of Natural Numbers." Disc. Math. 214, 123-133, 2000.Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, p. 126, 1974.Goulden, I. P. and Jackson, D. M. Problem 2.5.12 in Combinatorial Enumeration. New York: Wiley, p. 94, 1983.Hille, E. "A Problem in 'Factorisatio Numerorum.' " Acta Arith. 2, 134-144, 1936.Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., p. 141, 1985.Knopfmacher, A. and Mays, M. "Ordered and Unordered Factorizations of Integers." Mathematica J. 10, 72-89, 2006.MacMahon, P. A. "Memoir on the Theory of the Compositions of Numbers." Philos. Trans. Roy. Soc. London (A) 184, 835-901, 1893.Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, p. 124, 1980.Sloane, N. J. A. Sequence A074206 in "The On-Line Encyclopedia of Integer Sequences."Warlimont, R. "Factorisatio Numerorum with Constraints." J. Number Th. 45, 186-199, 1993.

Referenced on Wolfram|Alpha

Ordered Factorization

Cite this as:

Weisstein, Eric W. "Ordered Factorization." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/OrderedFactorization.html

Subject classifications