3
$\begingroup$

I have some questions as to some good combinatorial interpretations for the sum of elementary symmetric polynomials. I know that for example, for n =2 we have that:

$e_0 = 1$

$e_1 = x_1+x_2$

$e_2 = x_1x_2$

And each of these can clearly been seen as the coefficient of $t^k$ in $(1+x_1t)(1+x_2t)$. Now, in general, what combinatorial interpreations are there for say: $\sum_{i=0}^n e_i(x)$ for some $x = (x_1,...,x_n)$ ?

  • 0
    Mariano:I don't think it is, that's why I was asking. I probably stated myself incorrectly, what I meant to ask for is general combinatorial ways of viewing elementary symmetric polynomials and their sums.2011-01-31

4 Answers 4

5

$e_k(x_1,\dots,x_n)$ is the number of ways of picking a set of $k$ things from a set of $x_1+\cdots+x_n$ things, of which $x_1$ are of color $c_1$, $x_2$ are of color $c_2$, &c, in such a way that colors are not repeated.

Therefore $\sum_{k=0}^ne_k(x_1,\dots,x_n)$ is the number of ways of picking some elements out of those $x_1+\cdots+x_n$ things in such a way that their colors are different.

  • 0
    Steven:Right! So$e_k(x_1+1/x_1,...,x_n+1/x_n)$can be seen as the number of ways of assigning k things from a set of x_1+...+x_n things and x_1+...+x_n anti-things of which$x_1$are of color c_1 etc. so that colors are not repeated? Can one write this in the way of bins, as you said?2011-01-31
3

You nearly wrote the solution yourself: the sum of $e_i(x)$ for every $i$ is the sum of all the coefficients of the powers of $t$ in $(1+tx_1)\cdots(1+tx_n)$, that is, the value of this polynomial function at $t=1$, that is, $(1+x_1)\cdots(1+x_n)$. (I dunno if this counts as a combinatorial interpretation.)

3

Here are two specific interesting cases to go with Mariano Suárez-Alvarez's general explanation. On $n$ variables, $e_k(1,1,\ldots,1) = \binom{n}{k}$ and $e_k(1,2,\ldots,n) = \left[ n+1 \atop n-k+1 \right]$, where the latter is a Stirling number of the first kind. (See Comtet's Advanced Combinatorics, pp. 213-214.) So summing the former over $k$ gives $2^n$, and summing the latter over $k$ gives $(n+1)!$.

  • 0
    Also of note is the evaluation at $x_i=q^i$. (Starting from zero!)2011-01-31
0

A term in $e_k$ is the set of combinations of size $i$ from a set of size $n$. So the coefficient of a term in $\sum_{k=0} e_k$ is the number of combinations of -all- sizes, or rather, there is a one-to-one correspondence with the terms in the sum with the subsets of a set of size $n$.

  • 0
    Each coefficient in the polynomial $\sum_ke_k$ is $1$.2011-01-31