Let $M=(m_{ij})$ be a $n \times n$ matrix of variables. Then this number counts the number of "rooted" submatrices whose row indices match the column indices. By "rooted" I mean there is a distinguished element in the submatrix.
Left hand side. Since the row and column indices must match, there are $n \choose k$ submatrices with dimensions $k \times k$, each of which could have exactly $k^2$ roots. Summing this over $k$ gives $\sum_{k=0}^n k^2 {n \choose k}$ as the number of rooted matrices with matching row and column indices.
Right hand side. Now, lets re-do this count, but first choose the root cell $(i,j)$:
There are $n^2-n$ pairs $(i,j)$ for the root cell such that $i \neq j$. Once this is chosen, it belongs to $2^{n-2}$ submatrices with matching row and column indices.
There are $n$ pairs $(i,j)$ for the root cell such that $i=j$. Once this is chosen, it belongs to $2^{n-1}$ submatrices with matching row and column indices.
Hence, in total there are $(n^2-n) \cdot 2^{n-2}+n \cdot 2^{n-1}=n(n+1)2^{n-2}$ rooted matrices with matching row and column indices.