# Number of Non-Decreasing Sequences of Positive Integers with Product k

I was at the math.stackexchange site a few days ago and stumbled upon this question: How many ordered triples $(a,b,c)$ of positive integers?. While thinking of a solution for the problem, I realized that the general case, which I will state below, is in fact not so easy to solve:

Given a positive integer $k$, how many sequences of positive integers $a_i$ where $a_1 \leq a_2 \leq a_3 \leq ... \leq a_n$ have product $a_1a_2a_3...a_n=k$?

My solution for the specific case ($k=1000, n=3$) in the linked question was as follows.

Let $x, y, z$ respectively be the number of such sequences with no equal terms, a pair of equal terms and all three terms equal.

We first consider the number of positive integers $b_1, b_2, b_3$ that have product $k$, without placing the restriction that they must be non-decreasing. The prime factorization of $1000=2^3\times 5^3$ implies that the number of such sequences is simply ${{5}\choose{3}}^2=100$, since there are ${{5}\choose{3}}$ ways to distribute the powers of 2 among the three integers $b_i$ and similarly for powers of 5.

Therefore, we have

$$6x+3y+z=100$$

We can then check that, in the context of the problem, $z=1$, corresponding to the solution $[10,10,10]$, and that y=3, corresponding to the solutions $[1, 1, 1000], [2, 2, 250], [5, 5, 40]$ and thus we calculate that $x=15$, or $x+y+z=19$.

However, the solution doesn't easily generalize to higher $n$, at least as far as I can see, and the counting gets really complicated.

Is there a better approach to the question?

-