Faktorkombinationen

Faktorkombinationen describe the different ways a positive integer n can be written as a product of integers greater than 1. When the order of the factors is ignored, these representations are called multiplicative partitions of n; if order matters, they are called ordered factorizations or multiplicative compositions.

For example, for n = 12 the unordered factorizations are 12, 6×2, 4×3, and 3×2×2. If order is counted, these yield additional arrangements such as 2×6, 3×4, and the three permutations of 3×2×2 (2×3×2, 2×2×3).

In number theory the study of faktorkombinationer includes counting representations, understanding their structure, and enumerating them algorithmically. The function a(n) denotes the number of unordered factorizations of n into factors greater than 1 and is cataloged in the OEIS as A001055. In general there is no simple closed formula for a(n). For prime powers n = p^k, the number of unordered factorizations equals p(k), the ordinary partition function of k, since each factor corresponds to a summand in a partition of k.

Computational methods to enumerate multiplicative partitions typically use backtracking or dynamic programming. By recursively selecting factors in nondecreasing order, duplicates are avoided and all representations are generated efficiently.

See also: prime factorization, multiplicative partitions, integer partitions, OEIS A001055.