On a combinatorial identity involving elementary symmetric polynomials

Question

I'm trying to prove that if we have the elementary symmetric polynomials that the following identity holds:(where $x = (x_1,..,x_n)$ is a vector of n variables) $$\sum_{k=0}^n e_k(x)^2 = x_1\cdots x_n \sum_{j=0}^{\lfloor n/2 \rfloor} {2j \choose j} e_{n-2j}(x_1+1/x_1,\cdots x_n+1/x_n).$$ I'm trying to prove this combinatorially, but I'm stuck so I'd love some hints or tips.

Update: I guess we can get some interpretation with strictly increasing functions, but that thought isn't fully developed yet.

Answer 1

Consider the following experiment. There are $n$ boxes, with two identical coins each. We pick some $k \in \{0,\ldots,n\}$, pick $k$ coins from different boxes $A$, and then again pick $k$ coins from different boxes $B$. The left-hand side is exactly the generating function of all possible outcomes.

Here is another way of performing the same experiment. First choose a number $j < n/2$; this is going to be the size of $|A \setminus B| = |B \setminus A|$. Instead of choosing the elements in $(A \setminus B) \cup (B \setminus A)$, we will choose which elements are in $A \cap B$ and which in $\overline{A \cup B}$; we have to decide on $n-2j$ elements. If we start with assuming that each element is picked once (this is the factor $x_1\cdots x_n$), then putting an element $i$ in $A \cap B$ is like multiplying by $x_i$, and putting it in $\overline{A \cup B}$ is like multiplying by $1/x_i$. We are left with $2j$ elements, $j$ of which are in $A \setminus B$ and the rest in $B \setminus A$. There are $\binom{2j}{j}$ choices for that. Writing everything out, we get the right-hand side.

Answer 2

let $A$ be the invertible matrix whose eigenvalues are $x_1, . . . ,x_n$. We write $e_k(A)$ for $e_k(x_1,. . ., x_n)$. The generating function of the elementary symmetric polynomials:

$det(1+sA) = \sum_{k=0}^ne_k(A)s^k$

We have:

$\sum_{k=0}^ne_k^2=(2 \pi i)^{-1}\oint \frac{1}{s}det(1+sA)det(1+s^{-1}A) ds $

Where the integration is over a closed contour encircling the origin. (The contour integral just picks the coeficient of $s^0$). Therefore:

$\sum_{k=0}^ne_k^2=(2 \pi i)^{-1}\oint \frac{1}{s} det(A) (s+s^{-1})^n det(1+ (s+s^{-1})^{-1}(A+A^{-1})) ds $

$=\sum_{k=0}(2 \pi i)^{-1}\oint \frac{1}{s} (s+s^{-1})^k e_{n-k}(A+A^{-1}) ds $

Now, the polynomial $(s+s^{-1})^k$ has an $s^0$ only if k is even. Let k = 2j, then the binomial coefficient of $s^0$ is $2j \choose j $, which gives the required result.

Answer 3

Let $L$ be a a multiset whose elements are elements of $\{1,\dots,n\}$. Then the coefficient of $x^L$ (which is the product of the $x_i$ with $i\in L$, taking into account multiplicities) in $\sum_ke_k^2$ is the cardinal of the set $$X_L=\{(I,J)\in\mathcal P(\mathbf n)\times\mathcal P(\mathbf n):|I|=|J|, I\cup J=L\}.$$ Here $\mathbf n$ is the set $\{1,\dots,n\}$, $\mathcal P(\mathbf n)$ is the set of subsets of $\mathbf n$ (not multisets), and $I\cup J$ is the union taking into account multiplicities, whose result is a multiset.

Count the elements of the set $X_L$ in another way to obtain your equality.