3
$\begingroup$

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.

  • 6
    You don't have a set; what you have is a multiset because there are repetitions.2011-05-15

4 Answers 4

2

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.

  • 0
    Yeah, Gerry is right. That's what I want. This is the difficulty of this exam.2011-05-16
0

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

  • 0
    Depends a bit on what you mean by distinct products (or what Piseth means by distinct multiplications).2011-05-15
0

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?

0

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

  • 0
    @Gerry Agreed - however sometimes having a different solution may help find the correct answer, or at least provide insight to the problem at hand.2011-06-14