MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
A little playing with your sum shows that if you replace the appearance of n in the left hand side of your equation by a variable t, the right hand side becomes $2^{n^2}n!L_n(-(t-n)^2)$, with $L_n$ the $n$th Laguerre polynomial. Maybe this has a meaning? $${}$$ Extra points for introducing a $q$ somewhere in the left hand side and getting $q$-Laguerre polynomials on the right hand side! – Mariano Suárez-Alvarez Mar 5 '12 at 9:34
An unsuccessful approach is to weigh each summand by the number $e(G)$ of edges in $G$: we get $$\sum_{G\subseteq K_{n,n}} ~ q^{e(g)}\prod_{v\in V(G)} (t-2d_G(v)) = 4^n n! q^n (q+1)^{n^2-2 n} L_n\left(-\frac{((q+1) t-2 n q)^2}{4 q}\right).$$ – Mariano Suárez-Alvarez Mar 5 '12 at 10:02
(It is cute, though, how $2n$ of the factors of $2$ in the formula without the $q$s stay $2$s, while the other $n^2-2n$ become $(1+q)$s...) – Mariano Suárez-Alvarez Mar 5 '12 at 10:25
Out of curiosity, what is the average value of the product (I don't have the number of summands readily available, and you (@Brendan) probably do...) – Igor Rivin Mar 5 '12 at 17:53
So, the statement is that the expected value of the product is $n!.$ I find it really hard to believe that there is not a a simple way to see this (on the other hand, I am not seeing it right now :() – Igor Rivin Mar 5 '12 at 20:53
up vote 13 down vote accepted

I'm not sure if this is the right interpretation or 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).

share|cite|improve this answer
That's great. I'll add my proof in a few hours; you will see that it is somewhat parallel to yours. There is a nice generalization that I'll give too. – Brendan McKay Mar 5 '12 at 22:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.