Cómo encontrar a $\sum_{A \subset S} (\min A)$ $\sum_{A \subset S} (\max A)$ si $S=\{1,2,...,n\}$?

Question

Aquí, $\min A$ $\max A$ denotar el mínimo y el máximo del elemento, respectivamente, del conjunto de $A$.

Así que tengo que calcular cuántos subconjuntos de S min/max elemento $1$, ¿cuántos subconjuntos tiene min/max elemento $2$, ... todo el camino hasta $n$? No estoy siendo capaz de comprender intuitivamente el problema.

Quiero saber si hay una manera elegante de hacer esto.

Answer 1

Nota. Supongo que $m(\emptyset)=0$.

Pregunta. Consideremos el conjunto a $S=\{1,2,3,\dots,j\}$. Deje $m(A)$ denotar un máximo elemento de un subconjunto $A$$S$. Demostrar que $$\sum_{A\subseteq S}m(A) = (j-1)2^j+1$$ donde la suma de los rangos sobre todos los subconjuntos de a$A$$S$.

Solución. Consideremos el elemento $4$. $4$ será máximo del elemento si recogemos los elementos del conjunto $\{1,2,3,4\}$. Así que, básicamente, queremos contar el número de subconjuntos de un conjunto $\{1,2,3,4\}$ que contengan el elemento $4$. Este es el mismo como el conteo del número de subconjuntos de a$\{1,2,3\}$, y para cada subconjunto de $\{1,2,3\}$ añadimos el elemento $4$. Hay $2^3$ subconjuntos de a $\{1,2,3\}$, es decir, \begin{align*} \binom30 &= \{\emptyset\} \to \{4\}=\{4\}\\ \binom31 &= \{\{1\},\{2\},\{3\}\} \to \{4\}=\{\{1,4\},\{2,4\},\{3,4\}\}\\ \binom32 &= \{\{1,2\},\{1,3\},\{2,3\}\} \to \{4\}=\{\{1,2,4\},\{1,3,4\},\{2,3,4\}\}\\ \binom33 &= \{1,2,3\} \to 4=\{1,2,3,4\} \end{align*} Así que esto nos da una correspondencia entre los subconjuntos de a $\{1,2,3,4\}$ contiene $4$ y el subconjunto de $\{1,2,3\}$. Así que en general el subconjunto de $\{1,2,3,\dots,j\}$ contiene $j$ está en una correspondencia entre los subconjuntos de a $\{1,2,3,\dots,(j-1)\}$. Por lo tanto, la suma $$\sum_{A\subseteq S}m(A) = \sum_{i=1}^j i \cdot 2^{i-1}= (j-1)2^j+1.$$ Nota $1\cdot1+2\cdot2+3\cdot2^3+4\cdot2^3+\dots+n\cdot2^{n-1}= \frac{d}{dx} (x+x^2+x^3+\dots+x^n)_{x=2}$

Answer 2

Usted puede trabajar de forma recursiva. Para el mínimo: Indicar la suma de los mínimos con $m_n$ $$m_n:=\sum_{A\subset S_n}\min A$$ where $S_n=\{1,2,\dots,n\}$. Hence $S_n$ has $2^n$ subsets. Now consider the set $S_{n+1}=\{1,2,\dots,n,n+1\}$. The set $S_{n+1}$ has $2^{n+1}=2^n+2^n$ sets. The first $2^n$ sets are exactly the subsets of $S_n$ and the other $2^n$ are exactly the sets of $S_n$ with additionally the element $n+1$. So, the sum of the minimum of the first $2^n$ sets is again $m_n$ and the sum of the second $2^n$ is $m_n+(n+1)$ since $n+1$ is the minimum only of the set $\emptyset \cup \{n+1\}=\{n+1\}$. This gives you the recurrence relation $$m_{n+1}=2m_n+n+1$$ for $n\ge 0$, with $m_0=0$. Similarly, for the maximum you obtain the relation $$M_{n+1}=M_n+2^n(n+1)$$ for $n\ge 0$ with $M_0=0$.