21
$\begingroup$

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.

$\endgroup$
8
  • 4
    $\begingroup$ 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! $\endgroup$ Mar 5, 2012 at 9:34
  • 1
    $\begingroup$ 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).$$ $\endgroup$ Mar 5, 2012 at 10:02
  • $\begingroup$ (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...) $\endgroup$ Mar 5, 2012 at 10:25
  • $\begingroup$ 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...) $\endgroup$
    – Igor Rivin
    Mar 5, 2012 at 17:53
  • 2
    $\begingroup$ 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 :() $\endgroup$
    – Igor Rivin
    Mar 5, 2012 at 20:53

1 Answer 1

13
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Mar 5, 2012 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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