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)$ ?

$\endgroup$
3
  • $\begingroup$ Why is that a combinatorial interptetation? $\endgroup$ Jan 31, 2011 at 18:06
  • 1
    $\begingroup$ If you put dollar signs around your $\LaTeX$ it comes out pretty $\endgroup$ Jan 31, 2011 at 18:10
  • $\begingroup$ 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. $\endgroup$
    – Dedalus
    Jan 31, 2011 at 18:11

4 Answers 4

6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you, that was very helpful. If we set $e_k(x_1+1/x_1,...,x_n+1/x_n)$, are there any obvious combinatorial interpretation here? I don't see it, and I can't seem to extend your definition to this. $\endgroup$
    – Dedalus
    Jan 31, 2011 at 19:53
  • $\begingroup$ Dedalus: if $x_1$ represents a thing, then one way of looking at $1/x_1$ is as an 'anti-thing' - an item that when you combine it with your thing, gives you nothing. So, for instance, $(x_1+1/x_1)$ represents 'a thing or an anti-thing', and $(x_1+1/x_1)^n$ represents 'n (thing or anti-thing)s'; the constant coefficient of $(x_1+1/x_1)^n$ represents the number of ways of taking n (thing-or-anti-things) and combining them to get 0 - or, looked at another way, the number of ways of assigning n things to 2 bins such that there are equal numbers of things in the bins. $\endgroup$ Jan 31, 2011 at 21:19
  • $\begingroup$ 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? $\endgroup$
    – Dedalus
    Jan 31, 2011 at 22:08
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Also of note is the evaluation at $x_i=q^i$. (Starting from zero!) $\endgroup$ Jan 31, 2011 at 19:52
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Each coefficient in the polynomial $\sum_ke_k$ is $1$. $\endgroup$ Jan 31, 2011 at 18:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .