Introduction

To study the number of ways of writing a positive integer as a product of integer factors greater than one, there are two basic cases to consider. First, we can regard rearrangements of factors as different. In the case of , this gives the following eight ordered factorizations.

Alternatively we can ignore the order of the factors, which then gives the following four unordered factorizations.

These two functions, which we denote by and , respectively, can be considered multiplicative analogs of compositions and partitions of integers. A composition is an ordered set of positive integers that sum to . For example, we have eight compositions of , namely {{4}, {3,1}, {1,3}, {2,2}, {2,2,1}, {1,2,1}, {1,1,2}, {1,1,1,1}}. In general the number of compositions of , , is equal to . A partition is a set that sums to in which order is disregarded. There are five partitions of four. To count them we can use the function PartitionsP, and to list them we can use Partitions from the Combinatorica package.

In fact the number of compositions and partitions arise as special cases of our factorization functions, in the sense that if is a prime number, then and . For general numbers with prime factorizations , the enumeration of and is more complicated, as we shall discuss later.

We will also discuss factorizations into distinct parts. In the ordered case, since we have the factorizations {{2,6}, {3,4}, {4,3}, {6,2}, {12}}. In the unordered case, since there are three cases, {{4,3}, {6,2}, {12}}. If is a prime number, then as special cases we have and , where denotes the number of compositions of into distinct parts (see Richmond and Knopfmacher [1]), and PartitionsQ is the Mathematica function for counting partitions into distinct parts.

The enumeration and generation of integer partitions and compositions are problems discussed in standard books on combinatorics. A definitive reference is Andrews [2]. However, the corresponding problems for ordered and unordered factorizations have not until now received a comprehensive treatment.