Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.