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

Question

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!

Answer 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$.

Answer 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.$$

Answer 3

There are 5 types of possibilities for the unordered exponents $a_1,\cdots,a_5$ for 2:

$\textbf{1)}$ $6+0+0+0+0,\;\; 2+1+1+1+1$ $\;\;$(4 of a kind)

$\textbf{2)}$ $5+1+0+0+0,\;\; 3+0+1+1+1,\;\;4+2+0+0+0$ $\;\;$(3 of a kind)

$\textbf{3)}$ $4+1+1+0+0,\;\; 0+2+2+1+1$ $\;\;$(2 pairs)

$\textbf{4)}$ $3+3+0+0+0,\;\; 0+0+2+2+2$ $\;\;$(full house)

$\textbf{5)}$ $3+2+1+0+0$ $\;\;$ (1 pair)

---

Since we have the same 5 possibilities for the unordered exponents $b_1,\cdots,b_5$ for 5,

we can count the number of ways to pair up these types to get distinct divisors, using the fact that digits matched to repeated digits must be distinct, and their order doesn't matter:

$\textbf{1)}$ and 5) $\;$and$\;$ $\textbf{5)}$ and 1): $\;\;\;2(2\cdot1)(1)={\color{red}4}$ ways

$\textbf{2)}$ and 2): $\hspace{1.03 in}\;\;\;(3\cdot3)(1)={\color{red}9}$ ways

$\textbf{2)}$ and 3) $\;$and$\;$ $\textbf{3)}$ and 2): $\;\;\;2(3\cdot2)(2)=\color{red}{24}$ ways

$\textbf{2)}$ and 5) $\;$and$\;$ $\textbf{5)}$ and 2): $\;\;\;2(3\cdot1)(1+2\cdot3)=\color{red}{42}$ ways

$\textbf{3)}$ and 3): $\hspace{1.03 in}\;\;\;(2\cdot2)(1+2\cdot2)=\color{red}{20}$ ways

$\textbf{3)}$ and 4) $\;$and$\;$ $\textbf{4)}$ and 3): $\;\;\;2(2\cdot2)(1)=\color{red}{8}$ ways

$\textbf{3)}$ and 5) $\;$and$\;$ $\textbf{5)}$ and 3): $\;\;\;2(2\cdot1)(2\cdot3+3\cdot2)=\color{red}{48}$ ways

$\textbf{4)}$ and 5) $\;$and$\;$ $\textbf{5)}$ and 4): $\;\;\;2(2\cdot1)(3)=\color{red}{12}$ ways

$\textbf{5)}$ and 5): $\hspace{1.03 in}\;\;\;3\cdot3+3\cdot3\cdot2=\color{red}{27}$ ways

---

This gives a total of $\color{red}{194}$ ways of expressing $10^6$ as a product of 5 distinct positive integers.

Answer 4

There are 49 numbers of the form $2^\alpha 5^\beta$ with $0\leq\alpha\leq6$ and $0\leq\beta\leq 6$, and there are ${49\choose 5}=1\,906\,854$ sets of five different such numbers. Out of these five element sets exactly $194$ have product $10^6$. I found this using brute force. Handling the condition that the five factors should be different in an "automatic" way seems to transcend the usual inclusion-exclusion principle.

Answer 5

For $n{\ge}0$, $\;$ let $F(n)$ be the ways in which the number $10^n$ can be expressed as a product of five distinct positive integers.

Then $$F(n)=\left(\frac{1}{5!}\right)\left(24\left(\left\lfloor\frac{n}{5}\right\rfloor-\left\lfloor\frac{n-1}{5}\right\rfloor\right)^{2} +(-30)\left(\left\lfloor\frac{n}{4}\right\rfloor+1\right)^{2} +(-20)\left(\left\lfloor\frac{n+2}{2}\right\rfloor-\left\lfloor\frac{n+2}{3}\right\rfloor\right)^{2} +20\left(\left\lfloor\frac{(n+2)(n+3)}{6}\right\rfloor\right)^{2} +15\left(\frac{2n^{2}+10n+11+(2n+5)(-1)^n}{16}\right)^{2} +(-10)\left(\frac{4n^{3}+30n^{2}+68n+45+3(-1)^{n}}{48}\right)^{2} +\left(\frac{(n+1)(n+2)(n+3)(n+4)}{24}\right)^{2} \right)$$

The answer for this question is $F(6)=194$.

$$F(10)=6355,\quad F(100)=175519523577,\quad F(1000)=14758828112205481602.$$