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.
Best Answer
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).