While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone sees a nice interpretation. The sum is over all simple bipartite graphs $G$ with $n$ vertices on each side, the product is over all $2n$ vertices $v$ of $G$ and $d\_G(v)$ is the degree of vertex $v$ in graph $G$.
$$\sum\_{G\subseteq K\_{n,n}} ~ \prod\_{v\in V(G)} (n-2d\_G(v)) = 2^{n^2}n!~.\kern 3cm (1)$$


**Addition 1, proof.** Consider $n^2$ commuting indeterminates $\{x\_{ij}\}\_{i,j=1\ldots n}$. The polynomial
$$P(\boldsymbol{x}) = \prod\_{i=1}^n \sum\_{j=1}^n x\_{i,j} \times \prod\_{j=1}^n \sum\_{i=1}^n x\_{i,j}.$$
has terms with each variable having power 0, 1 or 2. Consider the total coefficient $C~$ of the terms with only even powers. One way is to sum each variable over $\pm 1$, which makes the terms we don't want cancel out and the others get multiplied by $2^{n^2}$. This gives (1), interpreting $G$ as the bipartite graph whose edges are the variables with value $-1$. Alternatively, note that each term has total degree $2n$ and the only possible such term with even degrees is $\prod\_{i=1}^n x\_{i,\sigma(i)}^2$ for some permutation $\sigma$. This shows $C=n!~$.


**Addition 2, generalisation.** Define the numbers
$$\rho(n,k,d) = \sum\_{j\ge 0} (-1)^j \binom{d}{j} \binom{n-d}{k-j}.$$
Let $k\_1,\ldots,k\_{2n}$ be a sequence of nonnegative integers. Then
$$\sum\_{G\subseteq K\_{n,n}} ~ \prod\_{v\in V(G)} \rho(n,k\_v,d\_G(v)) 
 = 2^{n^2} B(\boldsymbol{k}), $$
where $B(\boldsymbol{k})$ is the number of simple bipartite graphs with vertex $v$ having degree $k\_v$ for all $v$. The case (1) follows from $\rho(n,1,d)=n-2d$. The proof of the general case is similar.



A strange sum over bipartite graphs
I'm not sure if this is the right interpretation or not...it may really just be another way of encoding the generating function argument. Let $H$ be a random bipartite graph where every edge appears independently with probability $1/2$. Then the left hand side is 
$$2^{n^2} E \left(\prod\_v f(v) \right),$$
where $f(v)$ is equal to $\sum\_u x(u,v)$ and $x(u,v)$ is $1$ if an edge is not present, $-1$ if an edge is present. Expanding out the product and using linearity of expectation, we can write this as 


$$2^{n^2} \sum\_{\sigma} E \left(\prod\_{v} x(v,\sigma(v))\right)$$
Where $\sigma$ consists of all mappings taking each vertex to a vertex on the opposite side. 


Any $\sigma$ for which some edge $(v,\sigma(v))$ appears only once has $0$ expectation due to independence. The $\sigma$ for which every edge appears for both of its endpoints correspond to matchings between the left and right side, of which there are $n!$. (This last observation corresponds to the fact that the expected square of the permanent of an $n \times n$ random Bernoulli matrix is $n!$...I think it goes at least back to Turan). 


