Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Why is that a combinatorial interptetation? –  Mariano Suárez-Alvarez Jan 31 '11 at 18:06
1  
If you put dollar signs around your $\LaTeX$ it comes out pretty –  Ross Millikan Jan 31 '11 at 18:10
    
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. –  Dedalus Jan 31 '11 at 18:11
add comment

4 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
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. –  Dedalus Jan 31 '11 at 19:53
    
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. –  Steven Stadnicki Jan 31 '11 at 21:19
    
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? –  Dedalus Jan 31 '11 at 22:08
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
Also of note is the evaluation at $x_i=q^i$. (Starting from zero!) –  Mariano Suárez-Alvarez Jan 31 '11 at 19:52
add comment

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

share|improve this answer
    
Each coefficient in the polynomial $\sum_ke_k$ is $1$. –  Mariano Suárez-Alvarez Jan 31 '11 at 18:52
add comment

Your Answer

 
discard

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.