Demostrar que .

Question

Yo quiero probar el siguiente.

$$\sum_{A\subseteq [n]}\sum_{B\subseteq [n]} |A\cap B|=n4^{n-1}$$

Aquí es lo que he pensado hasta ahora:

Podemos tratar de subconjuntos de $[n]=\{1,2, \ldots, n\}$ como parte de una secuencia que consta de $1$s y $0$s, donde $1$ en la $k$th entrada indica que el $k$ es en el subconjunto y un $0$ indica que no lo es.

Cuando se comparan dos subconjuntos $A,B \subseteq [n]$ a un determinado $k$th entrada, hay $4$ posibilidades:

1) tanto en $A$ e $B$ tienen un $1$ a $k$th entrada,

2) $A$ tiene un $0$ e $B$ tiene un $1$ a $k$th entrada,

3) $A$ tiene un $1$ e $B$ tiene un $0$ a $k$th entrada,

4) tanto $A$ e $B$ tienen un $0$ a $k$th entrada.

Desde $0\leq k \leq n$, entonces hay $4^n$ posibilidades en total. Sin embargo, para cada una de las $k$ sólo una posibilidad contribuye a la suma, es decir, la posibilidad de (1), por lo que debemos dividir por 4 a contar cada una de las cuatro posibilidades como $1$, que es como creo que hemos $4^{n-1}$.

Tal vez esta es una falsa explicación, pero no veo donde la $n$ proviene.

Answer 1

Considere un experimento al azar, donde puedo elegir dos n-cadenas de bits $X$ e $Y$ independiente y uniformemente al azar de $\{0,1\}^n$ y contar el número de coordenadas en el cual ambas de las cadenas es uno. Vamos a identificar subconjuntos de $[n]$ con $n$-cadenas de bits. Tenemos \begin{align*} \mathbb E[|X\cap Y|] = \sum_{i=1}^n\mathbb E[|X_i\cap Y_i|] \end{align*} utilizando el hecho de que la expectación es lineal. Ahora si lanzas dos monedas de forma independiente, la probabilidad de que ambas sean jefes es $1/4$, por lo $\mathbb E[|X_i\cap Y_i|]=1/4$. Suma más de $n$ índices y normalizar por $2^n\times 2^n$, obtenemos la identidad que usted desea.

Answer 2

Usted puede comprobar esto por inducción.

Deje $S_n = \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} |A\cap B|,$ donde $[n] = \lbrace 1, \dots, n \rbrace.$ (estamos llevando $[0]$ a ser el conjunto vacío.)

Para $n\ge 0,$ los subconjuntos de $[n+1]$ que contengan $n+1$ como miembro son precisamente los conjuntos de la forma $A \cup \lbrace n+1 \rbrace,$ donde $A$ es un subconjunto de $[n].$

Los subconjuntos de $[n+1]$ que no contengan $n+1$ como miembro son precisamente los subconjuntos de $[n].$

Así

\begin{align} S_{n+1} &= \sum_{A\subseteq [n+1]}\sum_{B\subseteq [n+1]} \mid A\cap B \;\mid \\ &= \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap B\;\mid \\ & \hphantom{===} + \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid(A\cup \lbrace n+1 \rbrace)\cap B\;\mid \\ & \hphantom{===}+ \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap (B\cup \lbrace n+1 \rbrace)\;\mid \\ & \hphantom{===}+ \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid(A\cup \lbrace n+1 \rbrace)\cap (B\cup \lbrace n+1 \rbrace)\;\mid \\ &= \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap B\;\mid \\ & \hphantom{===}+\sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap B\;\mid \\ & \hphantom{===}+\sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap B\;\mid \\ & \hphantom{===}+\sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \big(1+\mid A\cap B\;\mid\big) \\ &= \left(\sum_{A\subseteq [n]}\sum_{B\subseteq [n]} 1\right) + 4 \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap B\;\mid \\ &= 2^n 2^n + 4 \sum_{A\subseteq [n]}\sum_{B\subseteq [n]} \mid A\cap B\;\mid \\ &= 4^n + 4 S_n. \end{align}

Con esta fórmula en la mano para expresar $S_{n+1}$ en términos de $S_n,$ es fácil de usar inducción para comprobar que $S_n=n\cdot 4^{n-1}$ para todos los enteros no negativos $n\!:$

La base $S_0=0$ es trivial.

Asumiendo $S_n=n\cdot 4^{n-1}$ como hipótesis de inducción, tenemos

\begin{align} S_{n+1} &= 4^n + 4 S_n \\ &= 4^n + 4 (n\cdot 4^{n-1}) \\ &= 4^n + n \cdot 4^n \\ &= (n+1)4^n, \end{align}

como se desee.

Answer 3

• El número de $k$ de los elementos de la $A\cap B$ puede variar de $0$ a $n$. Desde allí se $\binom{n}{k}$ posibilidades para seleccionar subconjuntos de tamaño $k$ de $[n]$, la contribución es \begin{align*} \sum_{k=0}^nk\binom{n}{k} \end{align*}

• Para cada una selección de $A\cap B$ del tamaño de la $k$ el tamaño de $A$ puede variar de $k$ a a $n$. Hay $\binom{n-k}{j}$ posibilidades para completar $A$ con $0\leq j\leq n-k$ elementos. La contribución es \begin{align*} \sum_{j=0}^{n-k}\binom{n-k}{j} \end{align*}

• Para cada una selección de $A$ del tamaño de la $k+j, 0\leq k\leq n, 0\leq j\leq n-k$ podemos seleccionar hasta a $n-k-j$ elementos de $[n]$ que no están en $A$ a completar $B$. Hay $2^{n-k-j}$ posibilidades para hacerlo.

Poniendo todo junto da: \begin{align*} \sum_{A\subset[n]}\sum_{B\subset[n]}|A\cap B|&=\sum_{k=0}^nk\binom{n}{k}\sum_{j=0}^{n-k}\binom{n-k}{j}2^{n-k-j} \end{align*}

Obtenemos para $n\geq 1$:

\begin{align*} \sum_{k=0}^nk\binom{n}{k}\sum_{j=0}^{n-k}\binom{n-k}{j}2^{n-k-j} &=\sum_{k=0}^nk\binom{n}{k}\sum_{j=0}^{n-k}\binom{n-k}{j}2^{j}\tag{1}\\ &=\sum_{k=1}^nk\binom{n}{k}3^{n-k}\tag{2}\\ &=n\sum_{k=1}^n\binom{n-1}{k-1}3^{n-k}\tag{3}\\ &=n\sum_{k=0}^{n-1}\binom{n-1}{k}3^{n-1-k}\tag{4}\\ &=n4^{n-1} \end{align*}

y el reclamo de la siguiente manera.

Comentario:

• En (1) podemos cambiar el orden de la suma en el interior de la suma: $j\rightarrow n-k-j$.

• En (2) se aplica el teorema del binomio.

• En (3) se aplica el binomio identidad $k\binom{n}{k}=n\binom{n-1}{k-1}$.

• En (4) el cambio en el índice de inicio de $k=0$ y aplicar el teorema del binomio de nuevo.

Answer 4

Cada$k\in[n]$ se cuenta una vez en la suma doble para cada par ordenado$\langle A,B\rangle$ de subconjuntos de$[n]$, de manera que$k\in A\cap B$. Arregla$k\in[n]$, y deja

PS

El mapa

PS

es una bijeccion, asi

PS

Por lo tanto, cada$$\mathscr{P}_k=\{\langle A,B\rangle\in[n]\times[n]:k\in A\cap B\}\;.$ se cuenta$$\varphi:\big([n]\setminus\{k\}\big)\times\big[n]\setminus\{k\}\big)\to\mathscr{P}_k:\langle A,B\rangle\mapsto\langle A\cup\{k\},B\cup\{k\}\rangle$ en la suma doble, que por lo tanto debe ser igual a$$|\mathscr{P}_k|=\left|\big([n]\setminus\{k\}\big)\times\big[n]\setminus\{k\}\big)\right|=\left(2^{n-1}\right)^2=4^{n-1}\;.$.

El argumento también puede llevarse a cabo como una manipulación de sumas:

$$ \begin{align*} \sum_{A\subseteq[n]}\sum_{B\subseteq[n]}|A\cap B|&=\sum_{A\subseteq[n]}\sum_{B\subseteq[n]}\sum_{k\in A\cap B}1\\ &=\sum_{k\in[n]}\sum_{k\in A\subseteq[n]}\sum_{k\in B\subseteq[n]}1\\ &=\sum_{k\in[n]}\sum_{k\in A\subseteq[n]}2^{n-1}\\ &=\sum_{k\in[n]}\left(2^{n-1}\cdot2^{n-1}\right)\\ &=\sum_{k\in[n]}4^{n-1}\\ &=n4^{n-1} \end {align *} $$