# What is the expected value of the number of anchors of $S$?

For any subset $S\subseteq\{1,2,\ldots,15\}$, call a number $n$ an anchor for $S$ if $n$ and $n+ |S|$ are both elements of $S$. For example, $4$ is an anchor of the set $S=\{4,7,14\}$, since $4\in S$ and $4+ |S| = 4+3 = 7\in S$.

Given that $S$ is randomly chosen from all $2^{15}$ subsets of $\{1,2,\ldots,15\}$ (with each subset being equally likely), what is the expected value of the number of anchors of $S$?

Write $T=\{1,\ldots,15\}$. Note that a set with fewer than $2$ elements cannot have an anchor. The expected value is $A/2^{15}$, where \eqalign{A &=\sum_{S\subseteq T}(\hbox{number of anchors of S})\cr &=\sum_{S\subseteq T}\sum_{n\in S}\cases{1&if n anchors S\cr 0&otherwise\cr} \cr &=\sum_{S\subseteq T}\sum_{n\in S}\sum_{k=2}^{15} \cases{1&if |S|=k, n+k\in S\cr 0&otherwise\cr}\cr &=\sum_{n=1}^{15}\sum_{k=2}^{15}\sum_{S\subseteq T} \cases{1&if |S|=k, n\in S, n+k\in S\cr 0&otherwise\cr}\cr &=\sum_{n=1}^{15}\sum_{k=2}^{15} \cases{0&if k>15-n\cr C(13,k-2)&otherwise.\cr}\cr } Reason for the last step: if $n+k>15$ there is no $S$ containing $n+k$, otherwise $S$ has $k$ elements of which two are already specified. Continuing, \eqalign{A &=\sum_{k=2}^{15}\sum_{n=1}^{15} \cases{0&if k>15-n\cr C(13,k-2)&otherwise\cr}\cr &=\sum_{k=2}^{15} (15-k)C(13,k-2)\cr &=\sum_{j=0}^{13} jC(13,j) } and this is a standard binomial sum, $$A=\sum_{j=1}^{13} 13C(12,j-1)=13\sum_{j=0}^{12}C(12,j)=13\times2^{12}\ .$$
Another exercise where the point is that the expected value of a sum is the sum of the expected values. Count the number of sets of size $k$ that have $j$ as anchor (thus they contain $j$ and $j+k$ and $k-2$ other members of $\{1,2,\ldots,15\}$.