Cómo calcular la suma de todos los elementos de un conjunto de potencia

Debe definir cuál es la suma de elementos de un conjunto de potencias que debe ser primero. Como sabe, los elementos del conjunto de potencias son subconjuntos del conjunto dado, y una adición para conjuntos no se define de forma inmediata.

Editar:
En los detalles de la pregunta, usted definió: {1} + {2 + 3} = 6. ¿Eso significa que define la suma de dos conjuntos como la suma de todos sus elementos? OK, pero por supuesto necesita que el conjunto original sea algo donde se define la suma, por ejemplo, números (como en su ejemplo).

Siguiente pregunta: ¿cómo define {1 + 2} + {2 + 3}? ¿Es esto 1 + 2 + 3 o 1 + 2 + 2 + 3?
Editar # 2: por aclaración en el comentario de respuesta, desea que las multiplicidades cuenten.
OKAY. Deje M tener n elementos.

Cada elemento de M está en un subconjunto de un elemento. Está en n-1 subconjuntos de dos elementos. Generalmente, si 1 <= k <= n, está en [math] \ binom {n-1} {k-1} [/ math] subconjuntos con k elementos.

Por lo tanto, cada elemento de M aparece en la suma una vez para cada una de sus ocurrencias en un subconjunto de M, que es [matemática] \ sum_ {k = 1} ^ {n} \ binom {n-1} {k-1} = \ sum_ {k = 0} ^ {n-1} \ binom {n} {k} = 2 ^ {n-1} [/ math] veces.

Por lo tanto, su suma es [matemáticas] 2 ^ {n-1} \ cdot \ sum_ {m \ en M} m [/ matemáticas]

Observación: Acabo de notar que la derivación del número de ocurrencias es demasiado complicada: obviamente, m está contenido exactamente en la mitad de los subconjuntos de M, entonces m ocurre [matemática] \ frac {2 ^ {n}} {2} = 2 ^ {n-1} [/ math] veces.

Hay una solución [matemática] O (n) [/ matemática] para este problema:

Suponga que ha evaluado la respuesta para los primeros elementos [matemáticos] (n-1) [/ matemáticos] del conjunto, donde hay elementos [matemáticos] n [/ matemáticos] en el conjunto. Denote la respuesta con [math] T_ {n-1} [/ math]. Deje que el elemento [math] n ^ {th} [/ math] del conjunto esté dado por [math] X_ {n}. [/ Math]

Luego:

[matemáticas] T_ {n} = (X_ {n} +1) T_ {n-1} + X_ {n}. [/ matemáticas]

Configurando [math] T_ {1} = X_ {1}, [/ math] y usando la ecuación recursiva anterior, se puede obtener [math] T_ {n} [/ math] en [math] O (n) [/ math ] hora.

Ejemplo para el conjunto de datos en detalles de la pregunta:

[matemáticas] T_ {1} = 1, [/ matemáticas]

[matemáticas] T_ {2} = (2 + 1) 1 + 2 = 5 [/ matemáticas]

[matemáticas] T_ {3} = (3 + 1) 5 + 3 = 23 [/ matemáticas]

Para el conjunto S = {1,2, …, n}, la respuesta es ((n * (n + 1)) / 2) * (2 ^ (n-1)).

Para ver por qué esto es cierto, observe que para cualquier número k en S, ocurrirá en la suma requerida 2 ^ (n-1) veces, porque el número de subconjuntos de S que contienen k es precisamente el número de subconjuntos de S \ {k} (que es igual a 2 ^ (n-1) para cualquier k).

Por lo tanto, la suma requerida es:
1 * (2 ^ (n-1)) + 2 * (2 ^ (n-1)) +… + n * (2 ^ (n-1))
= ((n * (n + 1)) / 2) * (2 ^ (n-1))

En general, para cualquier conjunto de números S, la suma requerida sería (SUM) * (2 ^ (n-1)), donde SUM es la suma de todos los elementos en S, como se desprende de la explicación anterior.

Respuesta: Suma (S) * 2 ^ (n-1)
Explicación: en el conjunto de potencia, cada número se producirá 2 ^ (n-1) veces,