Ordered Factorizations

For historical reasons, we will discuss formulas to enumerate factorizations before we discuss methods to generate the corresponding factorizations. In addition, some of the recursive methods to generate factorizations are extensions of the corresponding recursions to enumerate factorizations.

Recursions for Enumerating Ordered Factorizations

We begin with two recurrence formulas given by Hille [3]. The first element of an ordered factorization of can be any number such that divides . By appending to all possible ordered factorizations of , we obtain the recursion ; for . We implement this as follows.

Using the Möbius inversion formula, Hille also derived a second recursion,

where , which holds for .

This finds the list of distinct prime factors of .

This recursion requires the initial value .

The recursion can be rendered elegantly as a oneliner.

MacMahon's Formula for H

MacMahon [4] derived an explicit formula for the value of as a double sum over a product. Given ,

where , is the sum of the prime exponents of . We program this by

A Recursion for Factorizations with Distinct Parts

Warlimont [5] derived a Dirichlet series generating function for the function , which denotes the number of ordered factorizations of into distinct parts. Although Warlimont was only interested in this for asymptotic purposes, his generating function can be used to derive the following recurrence:

where the inside sum is taken over all such that and for , is a -st power.

There does not seem to be a simple combinatorial interpretation for this formula. We implement this starting with the appropriate boundary conditions.

When is a prime number we have the following.

Also observe that the number of parts must satisfy .

Now we implement the general formula.

We verify these counts by using the function DistinctOrderedFactorizations, which is defined in the next subsection.

To obtain the total number of distinct ordered factorizations, we must sum over all permissible values of the number of parts .

In practice this recursion is slow. A faster counting method is discussed in a later section.

Generating Ordered Factorizations

The first recursion for suggests a natural recursive approach to generate all the ordered factorizations of .

We append to the first factor in a factorization of , all possible ordered factorizations of , where can be any divisor of .

One way to list all the ordered factorizations with distinct parts is to simply select these from the list of all ordered factorizations.

However, there are faster methods for doing this, which we discuss in a later section.