# How to approach this problem of combinatorics

How many different numbers can be formed by the product of two or more of the numbers 3, 4, 4, 5, 5, 6, 7, 7, 7?

The question doesn't even make sense to me because it says "two or more," so I could pick $n$-many and there could be countably many. So that obviously doesn't make sense...But if I were to ignore that, what am I restricted to and why?

How would I then proceed from there?

## 1 Answer

You have a multiset containing one $3$, two $4$’s, two $5$’s, one $6$, and three $7$’s, for a total of $9$ elements. You must pick at least $2$ of these $9$ elements to form your product, and the question is how many different products you can form in this way.

A set of $9$ elements has $2^9$ subsets; one of them is empty, and $9$ have only one member each, so you’re down to $2^9-10$ subsets containing at least $2$ of these $9$ numbers. However, some of these subsets generate the same product. For instance, there are $\binom32=3$ ways to pick two of the $7$’s, so there are $3$ ways to get the product $49$. There are $2\cdot2=4$ ways to get the product $20$, since there are two $4$’s and two $5$’s. A case by case analysis like this looks very messy, however.

Notice that the only prime factors available are $2,3,5$, and $7$, so every product must have the form $2^a3^b5^c7^d$ for some non-negative integers $a,b,c,d$. It’s also clear that $a\le 5,b\le 2,c\le 2$, and $d\le 3$. One way to approach the problem is to count the $4$-tuples $\langle a,b,c,d\rangle$ that can actually be formed.

Suppose that we use the $6$, so that $a\ge 1$ and $b\ge 1$. The possible values of $a$ are then $1,3$, and $5$, depending on whether we use $0,1$ or $2$ of the $4$’s. The possible values of $b$ are $1$ and $2$. The possible values of $c$ are $0,1$, and $2$, and the possible values of $d$ are $0,1,2$, and $3$. That’s a total of $$3\cdot2\cdot3\cdot4=72$$ combinations, but one of them is $a=1=b$ and $c=d=0$, which uses only one of the $9$ numbers, namely, the $6$. Thus, there are $71$ different products that can be formed using the $6$.

Can you now count the products that can be made without using the $6$?

• So I shouldn't even be caring about what the actual products are? If I'm reading what you wrote correctly, this is almost like how many combinations I can make of 1 apple, 2 oranges, 2 pears, 1 kiwi, and 3 mangoes? – AlanH Jan 11 '13 at 23:57
• @Alan: No, the actual products matter. I’m in the process of extending my answer; it’s not done, but let me add what I have so far, since it will at least get you looking in the right general direction. – Brian M. Scott Jan 12 '13 at 0:00
• Shouldn't it be 144? I believe you're missing a 2. – AlanH Jan 12 '13 at 1:39
• @Alan: Where do you think that a $2$ is missing? – Brian M. Scott Jan 12 '13 at 1:49
• Nevermind! I was thinking for the general case. – AlanH Jan 12 '13 at 1:56