In how many ways can $1000000$ be expressed as a product of five distinct positive integers?

I'm trying to solve the following problem:

"In how many ways can the number $1000000$ be expressed as a product of five distinct positive integers?"

Here is my attempt:

Since $1000000 = 2^6 \cdot 5^6$, each of its divisors has the form $2^a \cdot 5^b$, and a decomposition of 1000000 into a product of five factors has the form $$ 1000000 = (2^{a_1} \cdot 5^{b_1})(2^{a_2} \cdot 5^{b_2})(2^{a_3} \cdot 5^{b_3})(2^{a_4} \cdot 5^{b_4})(2^{a_5} \cdot 5^{b_5}) $$ where $a_i$ and $b_i$ are nonnegative integers which satisfy the conditions $$ a_1 + a_2 + a_3 + a_4 + a_5 = 6, b_1 + b_2 + b_3 + b_4 + b_5 = 6 $$ The total number of systems of $a_i$ which satisfy the first equation is $210$ and the same number is for $b_i$. Thus the total number of decompositions is $210 \cdot 210 = 44100$. However, in this enumeration, factorizations which differ only in the brder of the factors have been counted separately; that is, some factorizations are counted several times each.

To get the number of distinct unordered decompositions I must, at first, substract the number of ordered decompositions with at least two identical factors and, at second, divide resulting number by $5!$ to leave only unordered ones.

And I'm stuck at the step of counting the number of ordered decompositions with at least two identical factors. The number of decompositions with $k$ identical factors is $(\lfloor\dfrac{a}{k}\rfloor + 1)(\lfloor\dfrac{b}{k}\rfloor+1){5 \choose k}$, that is, the number of decompositions with two identical factors is $16 \cdot {5 \choose 2} = 160$, three identical factors - $9 \cdot {5 \choose 3} = 90$, four ones - $4 \cdot {5 \choose 4} = 20$ and five ones - $4 \cdot {5 \choose 5} = 4$. Thus the number of distinct decompositions must be equal $\dfrac{44100-160-90-20-4}{5!}$, but this number is not integral. I suppose that the numbers of decompositions with $k$ identical factors overlap and I misuse inclusion-exclusion principle. But I have no idea how I can count that overlapped decompositions.

Please, help! Thanks!

Solution 1:

The number in question is the coefficient of $x^6 y^6 z^5$ in the product $$\prod_{0\le i,j\le 6}(1+x^i y^j z).$$ Here $z$ counts the number of factors (we want $5$); $x$ and $y$ tag the powers of $2$ and $5$ respectively; we want both of those to be $6$. Distinctness is ensured because, for each factor $2^i 5^j$, we either include it once (thereby multiplying by $x^i y^j z$) or we don't include it (and multiply by $1$).

Multiplying out the entire product is unwieldy, but you can compute it mod $(x^7,y^7)$, which eliminates a whole mess of terms you don't need. The coefficient of $x^6 y^6$ turns out to be $$5 z^7+64 z^6+194 z^5+235 z^4+123 z^3+24 z^2+z,$$ which enumerates the number of ways to write $1000000$ as a product of $k$ distinct factors, for all values of $k$. Taking $k=5$ we confirm Christian's answer of $194$.

Solution 2:

Let $F(n)$ be the ways in which the number $10^n$ can be expressed as a product of five distinct positive integers. Using the same strategy as in this MSE link (the Polya Enumeration Theorem or PET), we get the following answer in terms of the cycle index $Z(P_5)$ of the set operator $\mathfrak{P}_{=5}:$

$$[A^n B^n] Z(P_5)\left(\frac{1}{1-A}\frac{1}{1-B}\right).$$

The cycle index is $$Z(P_5) = {\frac {{a_{{1}}}^{5}}{120}}-1/12\,a_{{2}}{a_{{1}}}^{3}+1/6\,a_{{3 }}{a_{{1}}}^{2}+1/8\,a_{{1}}{a_{{2}}}^{2} \\-1/4\,a_{{4}}a_{{1}}-1/6\,a_{{2}}a_{{3}}+1/5\,a_{{5}}.$$

The substituted cycle index then becomes $${\frac {1}{120\, \left( 1-A \right) ^{5} \left( 1-B \right) ^{5}}} \\-1/12\,{\frac {1}{ \left( -{A}^{2}+1 \right) \left( -{B}^{2}+1 \right) \left( 1-A \right) ^{3} \left( 1-B \right) ^{3}}}\\+1/6\,{ \frac {1}{ \left( -{A}^{3}+1 \right) \left( -{B}^{3}+1 \right) \left( 1-A \right) ^{2} \left( 1-B \right) ^{2}}}\\+1/8\,{\frac {1 }{ \left( 1-A \right) \left( 1-B \right) \left( -{A}^{2}+1 \right) ^{2} \left( -{B}^{2}+1 \right) ^{2}}}\\-1/4\,{\frac {1}{ \left( -{A}^{4}+1 \right) \left( -{B}^{4}+1 \right) \left( 1-A \right) \left( 1-B \right) }}\\-1/6\,{\frac {1}{ \left( -{A}^{2}+1 \right) \left( -{B}^{2}+1 \right) \left( -{A}^{3}+1 \right) \left( -{B}^{3}+1 \right) }}\\+1/5\,{\frac {1}{ \left( -{A}^{5}+1 \right) \left( -{B}^{5}+1 \right) }}.$$

Extracting coefficients from this we get the pieces $$A_1 = \frac{1}{120} {n+4\choose 4}^2,$$ $$A_2 = -\frac{1}{12} \left(\sum_{q=0}^{\lfloor n/2 \rfloor} {n-2q+2\choose 2} \right)^2,$$ $$A_3 = \frac{1}{6} \left(\sum_{q=0}^{\lfloor n/3 \rfloor} {n-3q+1\choose 1} \right)^2,$$ $$A_4 = \frac{1}{8} \left(\sum_{q=0}^{\lfloor n/2 \rfloor} {q+1\choose 1}\right)^2,$$ $$A_5 = -\frac{1}{4} (\lfloor n/4 \rfloor+1)^2,$$ $$A_6 = -\frac{1}{6} \left(\sum_{q=0}^{\lfloor n/3 \rfloor} [[n-3q\equiv 0\mod 2]]\right)^2,$$ and $$A_7 = \frac{1}{5} [[n\equiv 0\mod 5]].$$

This yields the closed formula $$\frac{1}{120} {n+4\choose 4}^2 - \frac{1}{48} \left(\sum_{q=0}^{\lfloor n/2 \rfloor} (n-2q+2)(n-2q+1)\right)^2 \\ + \frac{1}{6} \left(\sum_{q=0}^{\lfloor n/3 \rfloor} (n-3q+1)\right)^2 + \frac{1}{32} (\lfloor n/2 \rfloor + 1)^2(\lfloor n/2 \rfloor + 2)^2 -\frac{1}{4} (\lfloor n/4 \rfloor+1)^2 \\ -\frac{1}{6} \left(\sum_{q=0}^{\lfloor n/3 \rfloor} [[n-3q\equiv 0\mod 2]]\right)^2 + \frac{1}{5} [[n\equiv 0\mod 5]].$$

Additional simplification is possible here but does not appear to add to the understanding of the problem. The sequence that we obtain starting with $n=1$ is $$0, 0, 1, 12, 53, 194, 548, 1369, 3064, 6355, 12295, 22608, \\ 39658, 66992, 109357, 173435, 267890, 404494, 598065, 868065, \ldots$$ which is in agreement with the earlier answer.

We also obtain $$F(1000) = 14758828112205481602.$$