Let $n\ge 1$ and $V_n = (\left\{ 1,2,...n \right\}\rightarrow\left\{ 0,1,2 \right\})$.
Let us define $G_n = \left<V_n, E_n \right>$. $f,g$, are two vertices. They are connected iff:
$$\left|\{ i \in \left\{ 1,...n\right\} | f(i)+g(i)=1 \right\}| = 1$$
Prove that the number of edges is: $$\sum\nolimits_{k = 0}^n {k\left( {\matrix{ n \cr k \cr } } \right)} {4^{k - 1}} \cdot {3^{n - k}}$$
My approach was "creating" a $2\times 2n$ table where the columns $(0,1), (1,0)$ are allowed to appear only once (and only one of them). I couldn't figure out how to connect this approach to the desired formula. I'll be glad for help!
If $f\in V_n$, let's define its paramater $k$ as $|\{i: f(i)\leq 1\}|$. Let's call $I_f=\{i: f(i)\leq 1\}$.
Let $f$ be a function of parameter $k$, and let's count its neighbours. We build a generic neighbour $g$. First, we have to choose the index $i$ for which $g(i)+f(i)=1$. This is only possible if $i\in I_f$, so we have $k$ choices for $i$. Then, we have to avoid $1$ on the other indices of $I_f$, so we have $2^{k-1}$ choices for $g$'s values on the rest of $I_f$. Finally, we can choose anything for the $n-k$ other values, so we have $3^{n-k}$choices.
In total, $f$ has $k2^{k-1}3^{n-k}$ neighbours.
Now, we just need to count the number of $f$ with parameter $k$. We have $n \choose k$ choices for the set $I_f$. Then, we have $2^k$ choices for the values of $I_f$, and none outside (it has to be $2$). So the number of $f$ with parameter $k$ is $2^k {n\choose k}$.
Finally, we sum all these neighbours for all $f$, and we get the formula $$2|E_n|=\sum_{k=0}^n2^k{n\choose k}\cdot k 2^{k-1} 3^{n-k}$$
Remember that the sum of degrees is twice the number of edges, because each edge is counted twice. Simplifying gives us the wanted formula.