6
$\begingroup$

How to find the numbers of sets of positive numbers $\{a,b,c\}$ such that $(a)(b)(c) =2^{4}3^{5}5^{2}7^{3}$ ?

$$\binom{4+2}{2} \binom{5+2}{2} \binom{2+2}{2} \binom{3+2}{2}$$

This would give the number of tuples $(a,b,c)$. But isolating the individual sets $\{a,b,c\}$ is harder as there would be duplicates. Any ideas how to do it?

$\endgroup$
3
  • $\begingroup$ Need $a,b,c$ be all different? $\endgroup$
    – kingW3
    Mar 8, 2017 at 13:13
  • $\begingroup$ @kingW3 Yes. I specifically mentioned that. $\endgroup$
    – user400242
    Mar 8, 2017 at 13:26
  • $\begingroup$ Allowing duplicates among $a,b,c$ would demand a multiset, as opposed to a set. $\endgroup$
    – MickLH
    Mar 8, 2017 at 13:27

3 Answers 3

7
$\begingroup$

Let $S = \{(a,b,c) \colon abc = 2^4 3^5 5^2 7^3\}$. Let's split it into few smaller sets. $S_1 = \{(a,b,c) \in S \colon a \neq b;\, b \neq c;\, a \neq c\}$, $S_2 = \{(a,b,c) \in S \colon a=b;\, b \neq c\}$ and let $S_3, S_4$ be similar to $S_2$ only with equal pairs $a=c$ and $b=c$. It's easy to notice that $S = S_1 \cup S_2 \cup S_3 \cup S_4$, because the case $a=b=c$ is impossible for our condition (otherwise all powers should be divisible by 3). Also $|S_2| = |S_3| = |S_4|$.

The answer for the problem is ${|S_1| \over 6}$, because each possible set of three elements contributes to $S_1$ six times. We know $|S|$ hence all we have to do is find $|S_2|$. It's quite easy, let's consider some element of $S_2$. $(a,a,b) = (2^{a_1} 3^{a_2} 5^{a_3} 7^{a_4}, a, 2^{b_1} 3^{b_2} 5^{b_3} 7^{b_4})$ and from our condition $$\left\{ \begin{array}{l} 2a_1 + b_1 = 4\\ 2a_2 + b_2 = 5 \\ 2a_3 + b_3 = 2\\ 2a_4 + b_4 = 3 \end{array} \right.$$ Each condition is independent from the others and there are $3$ possibilities to satisfy the first condition, $3$ for the second, $2$ for the third and $2$ for the fourth. So $|S_2| = 3 \cdot 3 \cdot 2 \cdot 2$. $|S_1| = |S| - 3 |S_2|$. We're done.

$\endgroup$
1
  • $\begingroup$ It's worth noting that the reason $a=b=c$ is impossible is that that would require all the exponents to be multiples of $3$. When you say "our condition" that makes me think of the "with no repeats" condition instead. $\endgroup$ Mar 8, 2017 at 14:34
1
$\begingroup$

As a check on the answer, we can explicitly find the sets with a short program. For example, in Python:

factors = sorted([2**i * 3**j * 5**k * 7**l for i in range(5) for j in range(6) for k in range(3) for l in range(4)], reverse = True)
sols = [[a, b, c] for a in factors for b in factors for c in factors if a*b*c == 2**4 * 3**5 * 5**2 * 7**3 and a > b and b > c]
len(sols)

which outputs 3132. This agrees with Artur Ryazanov's answer. (This is of course not the most efficient algorithm to generate the list of solutions - I've just found all the factors of the number and checked all 3-tuples.)

$\endgroup$
0
$\begingroup$

Stars and bars is indeed the valid approach for the tuples.

If you need the sets, you can deduplicate by ordering the sets (divide by $6$).

You'd have to modify the answer for $\{ a_1, a_2, a_3 \}$ where $a_1 = a_2$ or $a_2 = a_3$. They can't both be true.

You only need to determine $a_2$, that is of the form $2^{0,1,2}3^{0,1,2}5^{0,1}7^{0,1}$, since the two other terms can then be calculated.

$\endgroup$

You must log in to answer this question.