# How many distinct multiplications?

I have a multiset $\left\{ {2,3,3,3,4,4,5,5,6,7} \right\}$. How many distinct multiplications of three numbers chosen from the multiset?

e.g. $2×3×3$; $2×3×4$; $4×4×3$;... not $2×3×3$; $3×3×2$;... and $4×3×3$; $6×2×3$; ... (equal multiplication) are considered as the same.

-
By "distinct multiplications", do you mean distinct factors, or distinct results? (E.g., are $2\times 3\times 3$ and $1\times 3\times 6$ "distinct multiplications", or the same one?) – Arturo Magidin May 15 '11 at 3:52
You don't have a set; what you have is a multiset because there are repetitions. – Qiaochu Yuan May 15 '11 at 3:52

How many distinct products are there when all numbers are different? With two $3$'s, $4$'s or $5$'s? With three $3$'s?

-
Depends a bit on what you mean by distinct products (or what Piseth means by distinct multiplications). – Gerry Myerson May 15 '11 at 11:56

You can solve this using generating functions. For each number in your multiset, you can write a polynomial where the power of $x$ represents the number of times you choose a certain element from the set.

So you would have the polynomial $(1+x)$ representing the possibility of choosing or not choosing the number 2. Similarly $1+x+x^2+x^3$ represents the possibilities of choosing from the three available 3's in your list. Similarly, you have $1+x+x^2$ for the two 4's.

The answer you want is the coefficient of $x^3$ in the polynomial $(1+x)^3(1+x+x^2)^2(1+x+x^+x^3)$ which is 36.

If you are not familiar with generating functions, check out Herbert Wilf's generatingfunctionology for a detailed exposition.

EDIT: After Piseth changed his question to specify that the product has to be unique, I have to agree with Gerry's answer that there is no simple way to solve this other than to subtract repetitions from my answer.

-
This counts $2\times3\times6$ as different from $3\times3\times4$, even though both of them come to $36$. Of course, this may be what Piseth wants. Clarification is in order. – Gerry Myerson May 15 '11 at 11:54
@Gerry - This is how I interpreted his question. If he changes his question and my answer turns out to be wrong I'll gladly edit/delete my answer. – svenkatr May 15 '11 at 17:17
your answer was clear - I was asking for clarification from Piseth. – Gerry Myerson May 16 '11 at 0:00
Yeah, Gerry is right. That's what I want. This is the difficulty of this exam. – Piseth May 16 '11 at 12:21

Now that we have clarification from Piseth as to what was intended, it seems to me that there's no really nice way to do the problem. I'd say either bung it on a computer and let it count the number of different products, or use the methods suggested by svenkatr or Yuval to get a number from which you can subtract the duplications by hand. I don't think there are that many duplications: 2,6,7 and 3,4,7; 2,5,6 and 3,4,5; 2,4,6 and 3,4,4; 2,3,6 and 3,3,4; have I missed any?

-

I can contribute another generating function solution that answers the slightly easier question: How many distinct products can be made using only three numbers from the set $\{2,3,4,5,6,7\}$? Here we allow the product $7*7*2$ for example. This process is useful since it must be the upper bound for any multiset you give it.

The idea is simple, the product of any three numbers is going to be distinct if and only if the prime factorization is unique. Therefore we map each of the numbers like so:

2 -> x
3 -> y
4 -> x^2
5 -> z
6 -> xy
7 -> q


So the number $3*3*4 = y^2x^2$ is distinct from $2*3*4=x^3y$ but the same as the number $2*3*6=x^2y^2$. Now consider

$$P = x+y+x^2+z+xy+q$$

The number of distinct products is the number of terms in $P^3$ which we can ask a computer algebra system to compute. The upper bound for your problem $50$.

-
If you're going to ask a computer algebra system to find the number of terms in $P^3$, you might as well ask a computer to just solve the original problem by brute force. – Gerry Myerson Jun 14 '11 at 4:47
@Gerry Agreed - however sometimes having a different solution may help find the correct answer, or at least provide insight to the problem at hand. – Hooked Jun 14 '11 at 12:08