# Number of distinct decompositions

Given an integer $m$ as a product of integers $a_1,a_2,\ldots a_n$ I need to find the number of distinct decompositions of number $m$ into the product of $n$ ordered positive integers.

Example:
If $n=2$ and $a=(5,7)$ then answer will be $4$ since the possible ways of decomposing into ordered factors are $[7,5], [5,7], [1,35], [35,1]$.

Example 2: If $n=3$ and $a=(1,1,2)$ then answer will be $3$.

First form $N$, the product of all the numbers in $a$. We only care about the ordered ways to break $N$ into $n$ factors. Now factor $N$ into powers of primes: $N=\prod_ip_i^{b_i}$ We can consider each prime separately. For $p_i$ we want a weak compositionof $b_i$ into $n$ parts, which can be done in ${b_i+n-1 \choose n-1}$ ways. In total there are then $$\prod_i {b_i+n-1 \choose n-1}$$ ways to write $N$ as $n$ factors.

• please explain by example – user3001932 Feb 26 '14 at 17:08
• are u sure about this formula?How u come to it? – user3001932 Feb 26 '14 at 17:09
• Basically think about having $n$ bins that you divide the prime factors into. If you have five powers of 2 and $n=3$, this would say there are ${7 \choose 2}=21$ ways to distribute them, which you prove with a stars and bars argument. For each of these, you can distribute the $3$'s in however many ways, hence the product, and so on. – Ross Millikan Feb 26 '14 at 17:12

For $n=2$, this is equivalent to the number of divisors of $m$. Given $S:=\{a \in\mathbb N : a|m\}$ the ordered pairs can be constructed by $$O = \{(a, \frac ma) : a \in S\}$$ And thus $|O| = |S|$. This only depends on $m$, not directly on $a$.

$|S|$ can be easily calculated given the pfd of $m$. If $$m = \prod_{i=1}^k p_i^{n_i}$$ Where $p_i$ are distinct primes, then $$|O|=|S| = \prod_{i=1}^k (n_i+1)$$ In your case $m=35, p=(5,7), n=(1,1), |S|=(1+1)\cdot(1+1) = 4$

For general $n$ you can iterate the process to find $$|O(m,n)| = \sum_{a\in S(m)} |O(\frac ma, n-1)|$$ Where $|O(m,2)| = |S(m)|$.

Example:
If $n=3$ and $a=(5,5,7)$, then $m=5\cdot5\cdot7 = 175$. The divisors of $m$ are $$S(m) = \{1,5,7,25,35,175\}$$ So \begin{align*} O(m,3) & = O(\frac m1,2) + O(\frac m5,2) + O(\frac m7,2) + O(\frac m{25},2) + O(\frac m{35},2) + O(\frac m{175},2) \\ & = O(175,2) + O(35,2) + O(25,2) + O(7,2) + O(5,2) + O(1,2)\end{align*} Now \begin{align*} O(175,2) & = (2_5+1)(1_7+1) = 6 & \{(1,175), (5, 35), (7, 25), (25,7), (35,5), (175,1)\} \\ O(35,2) & = (1_5+1)(1_7+1) = 4 & \{(1,35), (5,7), (7,5), (35,1)\} \\ O(25,2) & = (2_5+1) = 3 & \{(1,25), (5,5), (25,1)\} \\ O(5,2) & = (1_5+1) = 2 & \{(1,5),(5,1)\} \\ O(7,2) & = (1_7+1) = 2 & \{(1,7), (7,1)\} \\ O(1,2) & = 1 & \{(1,1)\} \end{align*} And thus $O(175,3) = 6+4+3+2+2+1 = 18$. The elements in order considered are \begin{align*} O & = \{(1,1,175), (1,5,35), (1,7,25), (1,25,7), (1,35,5), (1,175,1)\} & (\text{from } O(175,2)) \\ &\cup \{(5,1,35), (5,5,7), (5,7,5), (5,35,1)\} & (\text{from } O(35,2)) \\ & \cup \{(7,1,25), (7,5,5), (7,25,1)\} & (\text{from } O(25,2)) \\ &\cup \{(25,1,7), (25,7,1)\} & (\text{from } O(7,2))\\ &\cup \{(35,1,5), (35,5,1)\} & (\text{from } O(5,2))\\ &\cup \{(175,1,1)\} & (\text{from } O(1,2)) \end{align*}

• what about second example ?How it comes to be 3 ? – user3001932 Feb 26 '14 at 16:37
• @user3001932 See my annotation for $n>2$. – AlexR Feb 26 '14 at 16:38
• @AlexsR n>2 or m>2 ? – user3001932 Feb 26 '14 at 16:42
• @user3001932 $n>2$. $m$ is given by $$m = \prod_{i=1}^n a_i$$ – AlexR Feb 26 '14 at 16:43
• I didnt get you .Is remaning general formula is |O|=|S|=∏i=1k(ni+1) – user3001932 Feb 26 '14 at 16:45