1

If you have $n$ numbers and you multiply them in every combination

$$A\cdot A,\ A\cdot B,\ B\cdot A,\ B\cdot B$$

and so on, how many times do you get the same answer? Or, how many times do you get a unique answer? That is just for a product of two numbers, what if you did product of $3, 4,... n$ numbers. Is there a formula that could calculate this?

An example would be, let's say you have numbers $2,3,5,7$. You can do

$$2\cdot 2,\; 2\cdot 3,\; 3\cdot 2, \;3\cdot 3, \;2\cdot 5, \;5\cdot 2, \;3\cdot 5, \; 5\cdot 3,\; 5\cdot 5,\; 2\cdot 7,\; 7\cdot 2, \;3\cdot 7, \;7\cdot 3, \;5\cdot 7,\; 7\cdot 5, \;7\cdot 7$$

With that you get 16 combinations and only 10 unique answers.

ki3i
  • 5,092
Joe
  • 534
  • For $n$ "generic" numbers (no two products are equal unless they must be) the number of distinct products is $\binom{n}{2}+n$, which is $\frac{n(n+1)}{2}$. – André Nicolas Apr 03 '15 at 15:32
  • Thank you, Ill have to do more research on the below, until then how could I convert the formula above for combination of three $S_1S_2S_3$ rather than just two? – Joe Apr 04 '15 at 21:26
  • You are welcome. Again we assume all products are distinct. .We can do it the long way, $\binom{n}{3}$ for all numbers different, $n(n-1)$ for two the same, one different, and $n$ for all the same, add. But there is a better way that generalizes to products of $k$ things, not necessarily different. It uses Stars and Bars, please see Wikipedia. For $k$ the count is $\binom{n+k-1}{k}$, so $\binom{n+2}{3}$ for products of three not necessarily distinct $S_i$. – André Nicolas Apr 04 '15 at 22:26

1 Answers1

2

We assume that we are given a set $S=\{s_1,s_2,\dots,s_n\}$ of $n$ distinct numbers, and want to count the number of numerically distinct products $a_1a_2\cdots a_k$, where the $a_i$ range over $S$.

The answer very much depends on numerical properties of the numbers in the set $S$. We will find the maximum possible number of numerically distinct products. We get this maximum if, for example, the elements of $S$ are distinct primes, and in many other cases.

Let $P$ be a product of $k$ elements of $S$. Let $x_1$ be the number of copies of $s_1$ that we used to form $P$. Let $x_2$ be the number of copies of $s_2$ that we used, and so on.

Then the $x_i$ are non-negative integers, and $x_1+\cdots+x_n=k$. Furthermore, under our assumptions any solution of $x_1+\cdots +x_n=k$ in non-negative integers gives a numerically distinct product.

Thus by Stars and Bars (please see Wikipedia) the number of numerically distinct products, under our assumptions, is $\binom{n+k-1}{n-1}$ or equivalently $\binom{n+k-1}{k}$.

Remark: The case $n=4$, $k=2$ of the OP does not require the above machinery, and neither does $n$ arbitrary, $k=2$. But note that for the case $k=2$, the general formula above gives the answer $\binom{n+1}{2}$.

André Nicolas
  • 507,029