Estoy teniendo un tiempo difícil encontrar el patrón. Supongamos que tenemos un conjunto
$$S = \{1, 2, 3\}$$
Los subconjuntos son:
$$P = \{ \{\}, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \}$$
Y el valor que estoy buscando, es la suma de las cardinalidades de todos estos subconjuntos. Es decir, para este ejemplo, $$0+1+1+1+2+2+2+3=12$$
¿Cuál es la fórmula para este valor?
Puedo ver un patrón, pero no puedo generalizar.
Aquí está una bijective argumento. Revisión de un conjunto finito $S$. Que nos permiten contar el número de pares de $(X,x)$ donde $X$ es un subconjunto de a$S$$x \in X$. Tenemos dos formas de hacerlo, dependiendo de coordinar arreglar primero.
Primera forma: Para cada conjunto $X$, $|X|$ elementos $x \in X$, por lo que el recuento $\sum_{X \subseteq S} |X|$.
Segunda forma: Para cada elemento $x \in S$, $2^{|S|-1}$ conjuntos de $X$$x \in X$. Tenemos todas ellas por la toma de la unión de $\{x\}$ con un subconjunto arbitrario de $S\setminus\{x\}$. Por lo tanto, el recuento $\sum_{x \in S} 2^{|S|-1} = |S| 2^{|S|-1}$.
Puesto que ambos métodos de recuento de la misma cosa, obtenemos $$\sum_{X \subseteq S} |X| = |S| 2^{|S|-1},$$ como en las otras respuestas.
Deje $N=|A|$.
Hay un conjunto de cardinal $0$, $N$ de cardenal $1$, ${N\choose2}$ del cardenal $2$, y, más generalmente, $N \choose k$ de cardenal $k$.
Así, por $N\ge1$ : $$\sum_{X \subseteq A}|X| = \sum_{k=0}^{N} k{N \choose k} = \sum_{k=1}^{N} N{N-1 \choose k-1} = N\sum_{k=0}^{N-1} {N-1 \choose k} = N 2^{N-1}$$
Esta fórmula se aplica también al $N=0$.
La lectura de la solución de Jack M me hizo pensar en otra estrategia que no puedo ayudar, pero post como una segunda respuesta, porque creo que es un espléndido argumento :)
Recordar el truco para encontrar la suma de $1+2+\ldots+n$.
Indicar la respuesta por $a$. Escribimos la suma dos veces, invirtiendo el fin de la segunda vez \begin{align*} a &= 1+2+3 & &&\ldots +n \\ a &= n + \ldots & &&+ 3 + 2 + 1 \\ \end{align*} Cada columna se suma a $n+1$, y $n$ columnas, por lo que tenemos $$\begin{align*} 2a = n(n+1) && \Longrightarrow && a= \frac{n(n+1)}{2} \end{align*}$$
Deje $S$ ser un conjunto con $n$ elementos. Queremos encontrar la suma de $|A_1| + |A_2| + \ldots + |A_{2^n}|$ donde $A_1,\ldots,A_{2^n}$ son todos los subconjuntos de a $S$. OK, vamos a jugar el mismo truco de nuevo!
Indicar la respuesta por $b$. Escribimos la suma dos veces, tomando el complemento de cada término del segundo tiempo \begin{align*} b &= |A_1|+|A_2|+|A_3| + \ldots +|A_{2^n}| \\ b &= |A_1^c|+|A_2^c|+|A_3^c| +\ldots +|A_{2^n}^c| \\ \end{align*} Cada columna se suma a $n$ e hay $2^n$ columnas, así que conseguir $$\begin{align*} 2b = n 2^n && \Rightarrow &&b = n 2^{n-1}. \end{align*}$$
De otra manera, una manipulación de sumatorias sin coeficientes binomiales:
$$\begin{align*} \sum_{A\subseteq S}|A|&=\sum_{A\subseteq S}\sum_{x\in A}1\\ &\overset{(1)}=\sum_{x\in S}\sum_{A\subseteq S\text{ s.t. }x\in A}1\\ &\overset{(2)}=\sum_{x\in S}2^{|S|-1}\\ &=|S|2^{|S|-1} \end{align*}$$
Paso $(1)$ es simplemente invirtiendo el orden de la suma, y de paso $(2)$ utiliza el hecho de que cada una de las $x\in S$ está en la mitad de los subconjuntos de a $S$, uno para cada subconjunto de $S\setminus\{x\}$.
Esto es realmente sólo un computacional versión de la idea básica de Mike F's argumento combinatorio.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
