Suma de productos de elementos de subconjuntos no vacíos de un conjunto A

Question

Sea $A_1, A_2, \ldots , A_{63}$ son los 63 subconjuntos no vacíos de $\{ 1,2,3,4,5,6 \}$ . Para cada uno de estos conjuntos $A_i$ , dejemos que $\pi(A_i)$ denotan el producto de todos los elementos de $A_i$ . Entonces, ¿cuál es el valor de $\pi(A_1)+\pi(A_2)+\cdots+\pi(A_{63})$ ?

He aquí la solución

Para el tamaño 1: suma de los elementos, que es 21 Para el tamaño 2 $ 1 \cdot (2 + 3 + 4 + 5 + 6) = 20 $ , $ 2 \cdot (3 + 4 + 5 + 6) = 36 $ , $ 3 \cdot (4 + 5 + 6) = 45 $ , $ 4 \cdot (5 + 6) = 44 $ , $ 5 \cdot 6 = 30 $ . La suma es 175. Para tamaño 3: Los de menor elemento 1: $ 6, 8, 10, 12, 12, 15, 18, 20, 24, 30 = 155 $ . Los que tienen menos elemento 2: $ 24, 30, 36, 40, 48, 60 = 238 $ . Los que tienen menos elemento 3: $ 60 + 72 + 90 = 222 $ . Los de menor elemento 4: sólo un subconjunto posible, que es $ \{4, 5, 6\} $ El $ \pi $ de los cuales 120. La suma total aquí es 735. Para el tamaño 4: Elemento menor 1: $ 24 + 30 + 36 + 40 + 48 + 60 + 60 + 72 + 90 + 120 = 580 $ al menos el elemento 2: $ 120 + 144 + 180 + 240 + 360 = 1044 $ ; menos elemento 3: sólo uno, que es $ 3 \cdot 4 \cdot 5 \cdot 6 = 360 $ . La suma total aquí es 1984. Para el tamaño 5: Excluya cada uno individualmente para obtener $ 720 + 360 + 240 + 180 + 144 + 120 = 1764 $ Para la talla 6: $ 6! = 720 $

La respuesta final es $ 21 + 175 + 735 + 1984 + 1764 + 720 = \boxed{5399} $

¿Hay alguna forma más corta de hacerlo?

Muchas gracias

Answer 1

Incluir el conjunto vacío en la suma (podemos restar al final)

La contribución de cada uno de los subconjuntos corresponderá a un término del siguiente producto \begin{eqnarray*} (1+1)(1+2)(1+3)(1+4)(1+5)(1+6) \end{eqnarray*} Así que la respuesta es $\color{red}{5039}$ .

En su pregunta los valores deben ser $21,175,735,\color{red}{1624},1764,720$ .

Answer 2

Yo tengo una forma de hacerlo, pero por alguna razón no obtengo el mismo resultado que tú.

Generalmente, si se tiene un conjunto finito $A$ de números, y quieres $\sum_{X\subseteq A}\prod_{x\in X}x$ el resultado será $\prod_{x\in A}(x+1)$ .

En su caso será $(1+1)(2+1)(3+1)(4+1)(5+1)(6+1)=2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7=5040$ : quita el producto vacío para $X=\emptyset, \prod_{x\in\emptyset}x=1$ y obtendrá el resultado final $5039$ .

Prueba : Inducción en $n=|A|$ . Para $n=0$ la igualdad se mantiene trivialmente. Supongamos que se cumple para todos los conjuntos de tamaño $n$ . Sea $A$ sea un conjunto de tamaño $n+1$ y que $a\in A$ y $B=A\setminus\{a\}$ . Ahora, podemos dividir todos los subconjuntos de $A$ en las que contienen $a$ y los que no:

$$\sum_{X\subseteq A}\prod_{x\in X}x=\sum_{X\subseteq B}\prod_{x\in X}x+\sum_{X\subseteq B}a\prod_{x\in X}x=(a+1)\sum_{X\subseteq B}\prod_{x\in X}x=(a+1)\prod_{x\in B}(x+1)\text{ (inductive hypothesis) }=\prod_{x\in A}(x+1)$$

Answer 3

Sea $X$ sea un conjunto que contenga $6$ gansos poniendo, $5$ anillos de oro, $4$ llamando a los pájaros, $3$ Gallinas francesas, $2$ tórtolas y $1$ partidario en un peral.

Para un $A \subseteq \{ 1, 2, 3, 4, 5, 6 \}$ el valor $\pi(A)$ es el número de maneras de escoger uno de cada uno de los animales (o anillos, supongo) de $X$ como indica $A$ . Por ejemplo, $\pi(\{2,5\})$ es el número de maneras de coger una tórtola y un anillo de oro de $X$ .

Así que $\sum_{A \subseteq X} \pi(A)$ es el número de maneras de (i) seleccionar un subconjunto de $[6]$ y ii) seleccionar uno de cada animal/anillo según lo indicado por ese subconjunto.

Este valor también puede calcularse, para cada $k \in [6]$ , decidiendo si va a elegir un animal/anillo según lo indicado por $k$ y, en caso afirmativo, seleccionar uno. Si se elige un animal/anillo, hay $k$ opciones para saber cuál elegir; si no, sólo hay $1$ elección (no elegir nada). Así $$\sum_{A \subseteq X} \pi(A) = \prod_{k=1}^6 (k+1) = 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7$$

Esto tiene en cuenta la posibilidad de no seleccionar nada, por lo que debemos restar uno, para obtener $$\sum_{i=1}^{63} \pi(A_i) = \sum_{\varnothing \ne A \subseteq X} \pi(A) = 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 - 1 = \boxed{5039}$$

Answer 4

Es sólo uno menos que el producto $$(1+1)(1+2)(1+3)(1+4)(1+5)(1+6)$$ Equivalentemente, es $f(1)-1$ donde $$f(x) = (x+1)(x+2)(x+3)(x+4)(x+5)(x+6)$$ Por las fórmulas de Vieta, los coeficientes de todas las potencias de $x$ que no sean $x^6,\;$ en la forma ampliada de $f(x)$ son las sumas de productos que desea.

Más concretamente, para $1 \le k \le 6$ el coeficiente de $x^{6-k}$ en la forma ampliada de $f(x)$ es la suma de todos los productos de $k$ elementos de $\{1,2,3,4,5,6\}$ .

Pero sumar esos coeficientes es lo mismo que sustituir $x=1$ en $f(x)$ excepto que hay que restar $1$ para corregir el sumando extra del término $x^6$ .

Answer 5

La respuesta es 5039 simplemente porque, si añades 1 (sea 1 el producto de los elementos del conjunto vacío) debes obtener $7!$ .

Se trata de una propiedad general: si $\pi(A)$ es el producto de los elementos de $A$ (con la convención $\pi(\emptyset)=1$ ), y $[n] = \{1,2,\dots, n\}$ entonces para cada $n$ $$ \sum_{A\subseteq [n]} \pi(A) = (n+1)!\,. $$ Es un hecho equivalente que $$ \sum_{A\subseteq [n]} \frac 1 {\pi(A)} = n+1\,, $$ como vemos dividiendo cada término por $n!$ (cada término $\pi(A)$ se convierte en $1/\pi(A^c)$ ).

Ambas se demuestran muy fácilmente por inducción, pero una prueba alternativa y una bonita interpretación probabilística de la segunda es la siguiente:

Estamos en el $(n+1)$ -ª planta, y tomamos un ascensor para bajar a la planta baja. Pero cada vez que pulsemos el botón, el ascensor se detendrá en un nivel aleatorio del trayecto, con probabilidad uniforme.

Sea $A$ ser el conjunto de niveles (plantas) donde el ascensor se detiene antes de que estemos abajo. Si llegamos allí en el primer paso entonces $A=\emptyset$ . Cuando estamos en el $k$ -ésimo piso, tenemos $k$ diferentes paradas posibles en la siguiente etapa. Por lo tanto, la probabilidad de cualquier $A$ ya que el conjunto de puntos intermedios es $1/\big((n+1)\,\pi(A)\big)$ y resumiendo para todos $A$ obtenemos $$ 1 = \frac 1 {n+1} \,\sum_{A\subseteq [n]} \frac 1 {\pi(A)}\,. $$