¿Cuál es el valor esperado del número de anclajes de $S$?

Question

Para cualquier subconjunto $S\subseteq\{1,2,\ldots,15\}$, llamar a un número $n$ un ancla para $S$ si $n$ $n+ |S|$ son elementos de $S$. Por ejemplo, $4$ es un ancla para el conjunto de $S=\{4,7,14\}$, ya que el $4\in S$$4+ |S| = 4+3 = 7\in S$.

Dado que el $S$ es elegido al azar entre todos los $2^{15}$ subconjuntos de a $\{1,2,\ldots,15\}$ (con cada subconjunto, es igual de probable), ¿cuál es el valor esperado del número de anclajes de $S$?

Answer 1

Escribir $T=\{1,\ldots,15\}$. Tenga en cuenta que con menos de $2$ elementos no tienen un anclaje. El valor esperado es $A/2^{15}$, donde $$\eqalign{Un &=\sum_{S\subseteq T}(\hbox{número de anclajes de $S$})\cr &=\sum_{S\subseteq T}\sum_{n\in S}\casos{1&si $n$ anclajes $S$\cr 0&lo contrario\cr} \cr &=\sum_{S\subseteq T}\sum_{n\in S}\sum_{k=2}^{15} \casos{1&si $|S|=k$, $n+k\in S$\cr 0&lo contrario\cr}\cr &=\sum_{n=1}^{15}\sum_{k=2}^{15}\sum_{S\subseteq T} \casos{1&si $|S|=k$, $n\in S$, $n+k\in S$\cr 0&lo contrario\cr}\cr &=\sum_{n=1}^{15}\sum_{k=2}^{15} \casos{0&si $k>15-n$\cr C(13,k-2) y de otra manera.\cr}\cr }$$ La razón para el último paso: si $n+k>15$ no es $S$ contiene $n+k$, de lo contrario $S$ $k$ elementos de los cuales dos ya se han especificado. Continuando, $$\eqalign{Un &=\sum_{k=2}^{15}\sum_{n=1}^{15} \casos{0&si $k>15-n$\cr C(13,k-2) y de lo contrario\cr}\cr &=\sum_{k=2}^{15} (15-k)C(13,k-2)\cr &=\sum_{j=0}^{13} jC(13), j) }$$ y este es un estándar binomio suma, $$A=\sum_{j=1}^{13} 13C(12,j-1)=13\sum_{j=0}^{12}C(12,j)=13\times2^{12}\ .$$

Answer 2

Otro ejercicio donde el punto es que el valor esperado de una suma es la suma de los valores esperados. Contar el número de conjuntos de tamaño $k$ que $j$ como ancla (por lo tanto contienen $j$ $j+k$ $k-2$ otros miembros de $\{1,2,\ldots,15\}$.