Factor triples

Over at JD2718, Jonathan asks the following question:

[A conference] presenter posed a problem that required finding three numbers that multiplied to make 72. The list included 1, 8, 9 and 2, 2, 18 and 3, 4, 6 and several other triples (groups of three numbers).

So I wondered, could we look at 72 and see how many factor triples it has? In general, how many factor triples does a number have?

Answering this question involves a lot of nice mathematics!

There are two different things this question could mean: it could be asking for the number of ordered triples (a, b, c) of positive integers such that a × b × c = n; or it could be asking for the number of multisets {a, b, c} (so that order doesn’t matter).  Equivalently, we could impose a particular order, like asking that a \leq b \leq c.  For example, the number 6 has two unordered factor triples (1×1×6 and 1×2×3) but nine ordered factor triples (1×1×6, 1×6×1, 6×1×1, 1×2×3, 1×3×2, 2×1×3, 2×3×1, 3×1×2, and 3×2×1).  As is often the case in combinatorics, the unordered factorization problem is much trickier, so let’s start with the ordered case.

The ordered case

Following Jonathan, first imagine that n is just a power of a single prime, say n = pk for some prime p and nonnegative integer k.  Then all of the factors a, b, and c must also be powers of p.  In fact, if we set a = px, b = py, and c = pz, then our original equation a × b × c = n gets transformed into the equation x + y + z = k, to be solved for nonnegative integers x, y, z.  This is the classic setting for stars and bars (the good kind, not the treason-in-defense-of-slavery kind); as the Wikipedia article explains, the number of solutions is exactly the binomial coefficient \binom{k + 2}{2} = \frac{(k + 2)(k + 1)}{2}. For example, when n = p is a prime number (so k = 1), there are \binom{3}{2} = 3 solutions (1×1×p, 1×p×1, and p×1×1), while if n = p2 is the square of a prime then there are \binom{4}{2} = 6 solutions (1×1×p2, 1×p2×1, and p2×1×1, 1×p×p, p×p×1, and p×1×p).

Now what if n is divisible by more than one prime?  Well, then the situations for the different primes are completely independent: for each prime, we have to choose how many of its factors go in the first coordinate, how many go in the second coordinate, and hand many go in the third coordinate.  So, for example, since 6 = 2×3, we have the following table of possibilities:

(1, 1, 2) (1, 2, 1) (2, 1, 1)
(1, 1, 3) 1×1×6 1×2×3 2×1×3
(1, 3, 1) 1×3×2 1×6×1 2×3×1
(3, 1, 1) 3×1×2 3×2×1 6×1×1

So that recovers exactly the nine solutions we had before.  In general, if n = p_1^{k_1} \cdots p_m^{k_m} is the prime factorization of n, then the number of ordered factor triples is \binom{k_1 + 2}{2} \cdots \binom{k_2 + 2}{2}.

The unordered case

To a first approximation, one should expect there to be six times as many ordered triples as unordered triples, since a typical unordered triple like {1, 2, 3} can be ordered in six different ways.  However, there are always triples like {1, 1, 6} (with two elements equal) that only have three different orderings, and even triples like {2, 2, 2} (with all three elements the same) that only have one ordering.  So the trick is going to be to figure out how many of each kind there are.

A single prime

Let’s start with the case of a single prime again.  As before, we’re studying the nonnegative integer solutions of the equation the equation x + y + z = k.  The unordered solutions of this equation, or equivalently the solutions such that x \leq y \leq z, are the integer partitions of k having at most three parts; however, rather than try to count these directly (which would lead to sequence A001399 in the OEIS), it will be more profitable to follow the ideas behind Burnside’s lemma and count ordered solutions based on how much duplication they have.

We know there are \binom{k + 2}{2} ordered solutions in total.  If k happens to be divisible by 3, then there is one solution with x = y = z, and otherwise there are none.  Now let’s think about solutions with y = z: in this case, the equation becomes x + 2y = k.  Counting solutions of this two-variable equation is easy: y can be any nonnegative integer up to (but not larger than) k/2, and for each such y there is exactly one value of x that works.  So the number of solutions in this case is \lfloor k/2 \rfloor + 1, where that bracket notation represents the floor function (rounding down to the nearest integer)<!– and we add one because the smallest allowable y is 0–>.  But we have to be a bit careful here: if k is divisible by 3, one of the solutions we’ve just counted is the solution with x = y = z.

So far we have the following cases: if k is a multiple of 3, there is 1 solution (x, x, x) and \lfloor k/2 \rfloor solutions (x, y, y) with x \neq y, while if k is not a multiple of 3 then there are \lfloor k/2 \rfloor + 1 solutions (x, y, y) with x \neq y.  And of course, for each ordered solution (x, y, y), there is also a solution (y, x, y) and a solution (y, y, x).  So if k is divisible by 3, we’ve accounted for 1 + 3 \lfloor k/2\rfloor ordered solutions, while if k is not divisible by 3 then we’ve accounted for 3\lfloor k/2\rfloor + 3 solutions.  Finally, all the other ordered solutions have all entries different, so they come in groups of six rearrangements, leading to \frac{\binom{k + 2}{2} - 3 \lfloor k/2\rfloor - 1}{6} unordered solutions if k is divisible by 3 or to \frac{\binom{k + 2}{2} - 3 \lfloor k/2\rfloor - 3}{6} unordered solutions if k is not divisible by 3.  (It isn’t obvious that these numbers are integers, is it?  But they have to be, as a consequence of our proof.  One could prove it directly by carefully considering all possibilities for the remainder upon dividing k by 6.)  If all we wanted was the total number of unordered solutions, we could add the three numbers from the previous paragraph up: for example, when k is divisible by 3, we get \frac{\binom{k + 2}{2} - 3 \lfloor k/2\rfloor - 1}{6} + \lfloor k/2\rfloor + 1 = \frac{\binom{k + 2}{2} + 3\lfloor k/2\rfloor + 5}{6} unordered solutions.  However, as we’ll see next, for purposes of combining different primes together, it’s really important that we know how many of each symmetry type there are.

Products of many primes

Having dealt with powers of a single prime, let’s move to the general case.  Suppose that n = p_1^{k_1} \cdots p_m^{k_m}.  First, let’s assume that n is not a perfect cube (so it cannot be written as a × a × a = n for integer a).  As we saw above, there are a total of \binom{k_1 + 2}{2} \cdots \binom{k_2 + 2}{2} ordered factor triples for n.  Almost all of these come in groups of six; the exceptions are the triples (a, a, b), with only three rearrangements.  To get such a triple, you need that simultaneously every single prime must divide the first two factors the same number of times.  As we saw when studying single primes, there are exactly \lfloor k_1/2 \rfloor + 1 ways to distribute the powers of p1 so that the first two factors get the same number of powers. Similarly, there are \lfloor k_2/2 \rfloor + 1 ways to distribute the powers of p2, and so on. Taking all the different primes into consideration, this gives (\lfloor k_1/2 \rfloor + 1) \cdot (\lfloor k_2/2 \rfloor + 1) \cdots (\lfloor k_m/2 \rfloor + 1) factor triples of the form (a, a, b). Since n is not a perfect cube, in each of these factorizations we have a \neq b, and so there exactly three permutations (a, a, b), (a, b, a), (b, a, a) of each such triple. That leaves \binom{k_1 + 2}{2} \cdots \binom{k_2 + 2}{2} - 3\left(\lfloor k_1/2 \rfloor + 1\right) \cdots \left(\lfloor k_m/2 \rfloor + 1\right) other ordered factor triples. We argued at the beginning of this paragraph that all of these triples come in groups of six rearrangements, so the total number of unordered factor triples is what we get by dividing this number by six and adding it to what we already had, namely

\dfrac{\binom{k_1 + 2}{2} \cdots \binom{k_2 + 2}{2} - 3\left(\lfloor k_1/2 \rfloor + 1\right) \cdots \left(\lfloor k_m/2 \rfloor + 1\right)}{6} + \left(\lfloor k_1/2 \rfloor + 1\right) \cdots \left(\lfloor k_m/2 \rfloor + 1\right),

which we can simplify somewhat to

\dfrac{\binom{k_1 + 2}{2} \cdots \binom{k_2 + 2}{2} + 3\left(\lfloor k_1/2 \rfloor + 1\right) \cdots \left(\lfloor k_m/2 \rfloor + 1\right)}{6}.

Finally, in the case that n is a perfect cube, we have to adjust the count slightly: among those ordered triples whose first two entries are equal, there is now one in which all three entries are equal. Making the necessary adjustments, we get in this case that there are

\dfrac{\binom{k_1 + 2}{2} \cdots \binom{k_2 + 2}{2} + 3\left(\lfloor k_1/2 \rfloor + 1\right) \cdots \left(\lfloor k_m/2 \rfloor + 1\right) + 2}{6}

factor triples.

For example, consider the factor triples of 1000 = 23 × 53. There are 10 ways to distribute the powers of 2 (three rearrangements of 1 × 1 × 8, six rearrangements of 1 × 2 × 4, and 2 × 2 × 2) and similarly 10 ways to distribute the powers of 5, so a total of 100 ordered factor triples. Of these, there are four in which the first two entries are equal: 1 × 1 × 1000, 2 × 2 × 250, 5 × 5 × 40, and 10 × 10 × 10. The first three of these have three permutations each, so this accounts for 1 + 3 × 3 = 10 of the 100 ordered factor triples. The remaining 90 triples come in 15 groups of six; their unordered representations are 1 × 2 × 500, 1 × 4 × 250, 1 × 5 × 200, 1 × 8 × 125, 1 × 10 × 100, 1 × 20 × 50, 1 × 25 × 40, 2 × 4 × 125, 2 × 5 × 100, 2 × 10 × 50, 2 × 25 × 40, 4 × 5 × 50, 4 × 10 × 25, 5 × 8 × 25, and 5 × 10 × 20. Thus, the total number of unordered factorization triples of 1000 is

19 = \dfrac{10 \cdot 10 + 3 \cdot 2 \cdot 2 + 2}{6},

as expected. For the original example 72 = 23 × 32 (so not a cube), we get

\dfrac{10 \cdot 6 + 3 \cdot 2 \cdot 2}{6} = 12

unordered factor triples.

TL;DR: OEIS

This sequence is number A034836 in the OEIS. My impression is that the conjectured formula there is equivalent to what I’ve worked out above, but I haven’t checked that carefully.

This entry was posted in Combinatorics, Education, Math and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s