Número de combinaciones de conjuntos sobre una función.

Question

¿Alguien sabe si la siguiente pregunta se ha resuelto en general o tiene alguna idea de la pregunta.

Tomemos por ejemplo los conjuntos {0,1} y {1,2} y la multiplicación de funciones (*) sobre los conjuntos se denotará como *(0,1)=0*1=0.

Ahora queremos saber el tamaño del conjunto que puede derivarse de la multiplicación sobre todas las combinaciones de tales conjuntos. Por ejemplo:

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

donde como

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

Se trata de un ejemplo sencillo, pero las generalizaciones a combinaciones del alfabeto superiores a dos deberían ser progresivamente más difíciles de seguir.

Answer 1

Voy a considerar que la pregunta es la siguiente: dado un conjunto $S$ de $n$ enteros no negativos, ¿cuántos números distintos hay de la forma $ab$ con $a,b$ en $S$ ?

Como OP sabe, la respuesta depende de $S$ no sólo en $n$ . He aquí algunos casos extremos.

1. Si $S=\{{0,1,2,4,8,\dots,2^{n-2}\}}$ entonces se obtiene $2n-2$ productos distintos. Esto es lo mínimo; no puede haber menos.

2. Si $S=\{{2,3,5,7,11,\dots,p_n\}}$ donde $p_n$ es el $n$ th prime, se obtiene $(n^2+n)/2$ productos distintos. Esto es lo máximo; no se puede conseguir más.

Si quieres una respuesta mejor, tienes que hacer algunas suposiciones sobre $S$ .