# Number of combinations of sets over a function.

Does anyone know if the following question has been solved in general or has any insight in the question.

Let us take for example the sets {0,1} and {1,2} and function multiplication (*) over the sets shall be denoted as *(0,1)=0*1=0.

We now want to know the size of the set that can be derived from multiplication over all combinations of such sets. For example:

{*(0,0), *(0,1), *(1,0), *(1,1)} = {0,1}

where as

{*(1,1), *(1,2), *(2,1), *(2,2)} = {1,2,4}

This is a simple example but generalisations to combinations of the alphabet larger than two should be progressively more difficult to keep track of.

-
– sai Jul 30 '12 at 15:11
Ah, excellent, sometimes you just need to know the right words. Thanks! – user1170304 Jul 30 '12 at 20:27

I'm going to take the question to be this: given a set $S$ of $n$ non-negative integers, how many distinct numbers are there of the form $ab$ with $a,b$ in $S$?

As OP is aware, the answer depends on $S$, not just on $n$. So here are some extreme cases.

1. If $S=\{{0,1,2,4,8,\dots,2^{n-2}\}}$ then you get $2n-2$ distinct products. This is the minimum; you can't get fewer.

2. If $S=\{{2,3,5,7,11,\dots,p_n\}}$, where $p_n$ is the $n$th prime, you get $(n^2+n)/2$ distinct products. This is the maximum; you can't get more.

If you want a better answer, you have to make some assumptions about $S$.

-
What do you mean by "minimum" and "maximum"? Are you taking this over all possible subsets of $\mathbb{Z}$? – Code-Guru Jul 31 '12 at 0:50
Minimum means minimum, and maximum means maximum. With $n$ non-negative integers (or even $n$ complex numbers), you can't have fewer than $2n-2$ distinct products, and you can't have more than $(n^2+n)/2$. – Gerry Myerson Jul 31 '12 at 2:16
Oops, I take back part of that comment. It's fine for non-negative integers, but with $n$ complex numbers you might have only $n$ products, if your $n$ complex numbers are the $n$th roots of unity. The $(n^2+n)/2$ part is OK for the complex numbers. – Gerry Myerson Jul 31 '12 at 2:54
Simply repeating a word doesn't define it. However, your additional comments do clarify to some extent what you are measuring the minimum and maximum of. – Code-Guru Jul 31 '12 at 17:48
@Code, I'm sorry, I'd be happy to clarify further, but I just don't know what needs clarification. Clarification is a two-way street - you have to make your needs clearer, too. – Gerry Myerson Aug 1 '12 at 3:17