Unordered Factorizations

There do not appear to be any explicit formulas for in the literature. Also, the recurrence relations that are known tend to lack simple combinatorial interpretations.

A Product Recursion

Harris and Subbarao [6] give the following product recursion for . For any positive integer , let if is an th power and otherwise. Let . This gives . To make use of this, we take logs of the recurrence. First, we define the values in terms of a given positive integer . One approach is to use Product.

Alternatively, here is a more elegant construction.

Then we can define P2.

The use of Simplify in P2 is not required, but speeds up the overall computation. Round produces the correct integer value for P2 much faster than by using additional simplification methods to remove the logarithms.

A Recursion for Unordered Factorizations with Largest Part m

Let denote the number of unordered factorizations of with largest part at most . Hughes and Shallit [7] gave the recursion

This particular recursion is easy to explain: Let be an unordered factorization of with parts at most and parts arranged in decreasing order, so that the largest part is . The number of ways to choose is then . For we can choose any divisor of such that . Summing over all such gives the result. We implement this as follows.

All unordered factorizations are counted by .

This gives a much faster recursion than P2.

Canfield, Erdös, and Pomerance [8] remarked in their paper that it is not particularly easy to compute . They mention that even showing takes some work. Their approach was based on a tree traversal algorithm. With our recursion this computation presents no problem.

Generating Unordered Factorizations

One inefficient approach is simply to sort the larger list of ordered factorizations and remove duplicates. However, a better approach is to use the Hughes-Shallit idea to recursively build up a list of ordered factorizations with largest part at most .

Now we test this out.

Unordered Factorizations with Distinct Parts

A modification of Hughes-Shallit reasoning gives a recursion for unordered factorizations with distinct parts and largest part at most . We merely observe that the part added to should have largest part less than or equal to :

We program this with necessary boundary conditions to start the recursion.

Here is an example.

Generating Unordered Factorizations with Distinct Parts

Again we can simply select the permissible factorizations from the larger list of all unordered factorizations, but a better approach is to recursively generate them using the idea for the recursion for .

Here are the distinct unordered factorizations of 24.

Here are the nondistinct factorizations.

We check that we are generating the right number of cases.

Faster Generation of Ordered Factorization Lists

The lists of unordered factorizations constructed earlier lead to a much faster way of generating the corresponding lists of ordered factorizations. We merely observe that all ordered cases arise as permutations of unordered cases. This gives a different ordering of the factorizations to the earlier method. However, the lists are easily checked to be the same.

The new approach gives a faster method for generating the factorizations list.

Factorizations with Distinct Parts

Again all ordered cases arise as permutations of unordered distinct cases. This also leads to a large speedup in computation time.

Faster Count for Ordered Factorizations with Distinct Parts

Let denote the number of unordered factorizations into distinct parts. We observe that . We do not have a formula for , but we can compute its values by sorting the lists of distinct unordered factorizations according to length. Although we generate (generally short) lists of factorizations as part of the counting process, this turns out to be the fastest method we have found to compute the usually large values of .

First, we sort our lists of factorizations according to length. For example, here .

Then, we split up the different classes with respect to length, count how many of length occur, multiply by , and sum.

This agrees with our previous computation. We put this method together as a oneliner.

In general, seems to provide a considerable speedup over .