1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ please explain by example $\endgroup$ – user3001932 Feb 26 '14 at 17:08
  • $\begingroup$ are u sure about this formula?How u come to it? $\endgroup$ – user3001932 Feb 26 '14 at 17:09
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Feb 26 '14 at 17:12
1
$\begingroup$

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*}$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.