# Number of different values that obtain from a given set

Suppose $$S=\{1,2,\dots,7\}$$, already we know that, $$S$$ have $$2^7$$ subsets. But the problem is, when we multiply elements of each subset $$S$$, how many different value we can obtain from multiplication of elements of each subsets? In $$2^7$$ subsets, some of them are equal, for example, for subset of size 2, $$3\times 4=6\times 2$$. Are there a simple way that eliminate the duplicate values for any subsets?

• It's usually nice to add some context (from where is this problem) and some thoughts or early attempts you've done. As a hint, I'd start with writing the possible factorizations in primes of numbers you can obtain from the set $S$. Jul 29 '21 at 9:39
• Every number you get is a divisor of $7!=5040$. But you can't get every divisor of $5040$, e.g., you can't get $9$. That should get you started. Jul 29 '21 at 11:08
• That is already a huge hint. The hint in more words again is that the odd multiples of $9$ who are divisors of $7!$ are not possible. Can you think of any others who are not possible? Can you prove that? Note that the only prime factors possible in the results are $2,3,5,7$ which limits the search considerably. Jul 29 '21 at 12:49
• Now... $7! = 2^4\cdot 3^2\cdot 5\cdot 7$... The number of factors of a number is well known to be the product of one more than each of the exponents in the prime factorization... in this case $(4+1)\cdot (2+1)\cdot (1+1)\cdot (1+1)=5\cdot 3\cdot 2\cdot 2 = 60$, and the number of these which are not possible you can count simply as well and remove from the count. Jul 29 '21 at 12:54

$$7!=2^4\cdot 3^2\cdot 5^1\cdot 7^1$$ has $$(4+1)(2+1)(1+1)(1+1)=60$$ divisors

Of these, the divisors who are multiples of $$2^4$$ but not multiples of $$3$$ are not possible to make (as $$6$$ would have been needed for that last factor of $$2$$ and would have brought a factor of $$3$$ along with it) as well as the divisors who are multiples of $$9$$ but not multiples of $$2$$ are not possible (for a similar reason).

There are $$2\cdot 2 = 4$$ factors who are multiples of $$2^4$$ but not multiples of $$3$$ (seen by looking at factors of the form $$2^4\cdot 3^0\cdot 5^z\cdot 7^w$$) and similarly there are $$2\cdot 2 = 4$$ factors who are multiples of $$9$$ but not multiples of $$2$$ (looking at $$2^0\cdot 3^2\cdot 5^z\cdot 7^w$$).

As such the total will be

$$60 - 4-4 = 52$$

Since $$1$$ has no effect in the multiplications you can put it aside. Put the number $$6$$ aside for now. Factorize all the other numbers. The multiplication of the elements of any nonempty subset of $$\lbrace 2, 3, 4, 5, 7 \rbrace$$ would be of the form $$2^{x} \times 3^{y} \times 5^{z} \times 7^{w}$$ where $$x$$ and $$y$$ and $$z$$ and $$w$$ are whole numbers and $$0 \leq x \leq 3$$ and $$0 \leq y \leq 1$$ and $$0 \leq z \leq 1$$ and $$0 \leq w \leq 1$$. As a result of the multiplication principle, you can say that there are $$4 \times 2 \times 2 \times 2 = 32$$ such multiplications. Now what if we play the number $$6$$ into the game? Then any multiplication would be of the form $$2^{x + 1} \times 3^{y + 1} \times 5^{z} \times 7^{w}$$ where $$x$$ and $$y$$ and $$z$$ and $$w$$ are whole numbers and $$0 \leq x \leq 3$$ and $$0 \leq y \leq 1$$ and $$0 \leq z \leq 1$$ and $$0 \leq w \leq 1$$. However, if $$0 \leq x \leq 2$$ and $$y = 0$$ no new state will be generated and vice versa so you should suppose either $$x = 3$$ or $$y = 1$$. You can deduce from the inclusion-exclusion principle that the number of the new states will be $$2 \times 2 \times 2 + 4 \times 2 \times 2 \; - 2 \times 2 = 20$$. So overall the answer would be $$32 + 20= 52$$.

• You overcounted the divisor $1$. It appeared in not only your first case (where you considered only the divisor $1$) but also in your second case where you considered divisors of the form $2^x3^y5^z7^w$ in the case of $x=y=z=w=0$. Note, the empty-product is equal to $1$. Jul 30 '21 at 12:07
• Yes. I made a mistake. You're right. I'll edit it. Good point.