The Last Row of the Inverse of a Matrix The sparse matrix $A$ of size $2^n-1$ is defined as follows: 
all diagonal elements $a_{i,i}$ are $1$, and $a_{i,j}$ is $-\frac{1}{n}$ if and only if the binary representations of $i$ and $j$ have only ONE different bit. 
For example, when $n=2$, $$A=\begin{pmatrix} 
1 & 0 & -\frac{1}{2} \\
0 & 1 & -\frac{1}{2} \\
-\frac{1}{2} & -\frac{1}{2} & 1
\end{pmatrix}$$ I'd like to ask what is the last row of the inverse of $A$?
 A: Interestingly, this looks like the difference between the identity matrix $I$ and (a scaled version of) the adjacency matrix $G$ for a certain graph. The graph has one node for each number in $1\ldots 2^n-1$; two numbers are connected if their binary representations differ by exactly one bit (so no self-loops). (Edit: this graph has a name; it's the the hypercube graph $Q_{n+1}$)
The inverse of $(I-\frac{1}{n}G)$ is related to the Leontief Inverse of $G$. Note that, if this inverse exists, we can expand it as the infinite sum:
$$\left(I-\frac{1}{n}G\right)^{-1} = I + \frac{1}{n}G + \frac{1}{n^2}G^2 + \ldots + \frac{1}{n^k}G^k + \ldots$$
(To see that this is true, multiply both sides by $(I-G/n)$.)
In terms of graph theory, $G^k$ counts the number of distinct $k$-step paths between pairs of nodes. In this case, $G^k$ counts the number of distinct ways of converting the binary representation of $i$ into the binary representation of $j$ by changing one bit at a time. For example, a two step path might be $1 \rightarrow 3 \rightarrow 2$ $(\mathtt{01}\rightarrow\mathtt{11}\rightarrow\mathtt{10})$.
When two paths convert $i$ to $j$ by changing the same bits in a different order, each will be counted separately, as in $1\rightarrow 3 \rightarrow 7$ and $1\rightarrow 5 \rightarrow 7$. Also you are allowed to flip a bit then flip it back, as in $1\rightarrow 3\rightarrow 1\rightarrow 5$.
I do not see a concise way of explaining what the last row of this inverse is, except to say that it is a weighted sum—over all $k$—of the $k$-step ways of turning  the max number $2^n-1$ into each other number $1\ldots 2^{n}-1$.

By the way, if you include 0 in this graph, then every node has $n$ neighbors because you can change a bit in any of the $n$ positions (so $G$ is a regular graph of degree $n$). If you don't include zero, then the powers of two have only $n-1$ neighbors (because their bitwise representation has only one $\mathtt{1}$, and they don't have 0 as a neighbor). The graph $G$ is also bipartite, because by flipping one bit you can turn numbers with an odd number of $\mathtt{1}$s into numbers with an even number, and vice versa, but never even->even or odd->odd.

Also by the way, the number of $k$-step paths turning $i$ into $j$ depends on how many places $p$ at which $i$ and $j$ differ. If $k<p$, there's no way to convert them. If $k=p$, then there are $p!$ ways to convert them, corresponding to flipping the $p$ bits in any order you like. At higher values of $k$, the number of paths depends on whether $k-p$ is even or odd. If it's even, you can change $i$ into $j$, then toggle some bits back and forth so that the result is still $j$ by the end. If it's odd, you're out of luck because you'll always have at least one bit that isn't right.
In the even case, you must change $p$ bits. You must also choose any $(k-p)/2$ places (not necessarily distinct) to toggle back and forth. There are $n^{(k-p)/2}$ options. And you can perform the changing of bits and the flip-flops intermixed in any order; this can happen in some further complicated number of ways, especially considering that the $(k-p)/2$ places are not necessarily distinct so symmetry must be taken into account.
A: This is more of a comment than actual answer, but maybe too long so let's put it here as answer.
If you only want to calculate the sum of last row, I think it can be done like this: Notice that each $n$-bitstring (that is vertex of the $n$-cube) that has $r$ ones is in symmetric position when you start from $11\dots 1$. You can reduce the situation to letting the state $r$ be how many zeros there are. Then calculate the expected number of transitions to go from $r$ to $r+1$, denote that $a_r$, with a recursion similar to one in this question
Now for the total number of transitions sum these up and arrive at the formula given here.
(Note: in those you go from $00\dots 0$ to $11\dots 1$, but these are just notational differences).
Also see OEIS sequence (The sequence (origin 1) is the resistance between opposite corners of an n-dimensional hypercube of unit resistors, multiplied by n!)
So, as said this is only for the sum, I don't see how to turn those $a_r$'s to the number of expected visits (which are the elements of the last row of $A^{-1}$).
