The Eulerian numbers enjoy many different presentations among which I write the two-variable recursive definition: $A(n,0)=1$ and $A(n,k)=0$ for $k<0$ so that $$A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1).$$ However, my curiosity is regarding a certain "vanishing-variables" formulation (summation) over the symmetry (permutation) groups $\mathfrak{S}_n$:

QUESTION. For $0\leq k\leq n$ and a set of variables $x_1, x_2, \dots, x_{n+1}$, experiments suggest $$A(n,k)=\sum_{\pi\in\mathfrak{S}_{n+1}}(x_{\pi(1)}+\cdots+x_{\pi(k+1)})^n\prod_{i=1}^n\frac1{x_{\pi(i)}-x_{\pi(i+1)}}.$$ It seems correct to me. Proof or disproof? I am still hoping and waiting.

  • $\begingroup$ What is $k$? Should it be $i$? $\endgroup$ – Ira Gessel Dec 15 '16 at 0:17
  • $\begingroup$ Thanks, but it is not a typo. The numerator does not depend on $i$. The $k$ reflects the one on the LHS. I rewrote the RHS so as not to confuse anyone. $\endgroup$ – T. Amdeberhan Dec 15 '16 at 0:19
  • $\begingroup$ My mistake—sorry. $\endgroup$ – Ira Gessel Dec 15 '16 at 0:22
  • $\begingroup$ Are you sure about the "rt.representation-theory" tag? That usually refers to linear representations of group, not of the kind of representation you're asking for; it's true that there's a lot of combinatorics bound up in the representation theory of the symmetric group, but as it stands that combinatorics is not visible here. $\endgroup$ – Noam D. Elkies Dec 15 '16 at 1:31
  • 3
    $\begingroup$ Shouldn't Theorem 3.1 in arxiv.org/abs/math/0507163v1 (applied to $n = n+1$ and $x_i = \begin{cases} 1, & \text{ if } i \leq k+1; \\ 0, & \text{ if } i > k+1 \end{cases}$) reveal that your right hand side is $n! \operatorname{Vol} P_{n+1}\left(\underbrace{1,1,\ldots,1}_{k+1 \text{ entries}}, \underbrace{0,0,\ldots,0}_{n-k \text{ entries}}\right) = n! \operatorname{Vol} \Delta_{k+1,n+1}$ ? And identifying this with the left hand side is the classical geometric interpretation of Eulerian numbers? $\endgroup$ – darij grinberg Dec 15 '16 at 3:34

Quiet a short algebraic proof may go as follows (I cite my own manuscript). For a polynomial $f(x_1,\dots,x_{n+1})$ of degree at most $n$ we define a linear operator $$\Phi[f]=\text{Sym}\, \frac{f(x_1,\dots,x_{n+1})}{(x_1-x_2)(x_2-x_3)\dots (x_n-x_{n+1})},$$ where $\text{Sym}\, g(x_1,\dots,x_{n+1})=\sum g(x_{\pi_1},\dots,x_{\pi_{n+1}})$, the summation is over all $(n+1)!$ permutations of the variables. Note that $\Phi[f]$ is actually a polynomial of degree at most 0 (all factors in the denominator are cancelled, see Ilya's comment), in other words, it is a scalar, and the linear operator $\Phi$ is a linear functional.

Several observations about $\Phi$.

1) If $f$ is divisible by $y:=x_1+\dots+x_{n+1}$, then $\Phi[f]=y\Phi[f/y]=0$. (The same holds for any symmetric factor $y$.)

2) Assume that $f=(x_{k}-x_{k+1})h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. Then $$\Phi[f]=\begin{cases}\binom{n+1}k\Phi_k[h]\Phi_{n+1-k}[g],\,\text{if}\deg h=k-1\,\text{and} \deg g=n-k\\ 0,\,\text{otherwise}\end{cases}.$$

3) If $f$ is divisible by $(x_1+\dots+x_k)(x_{k}-x_{k+1})$, then $\Phi[f]=0$. Indeed, it suffices to consider the polynomials $f=(x_1+\dots+x_k)(x_{k+1}-x_k)h(x_1,\dots,x_k)g(x_{k+1},\dots,x_{n+1})$. For them the claim follows from 1) and 2).

Before proving your Euler numbers claim we prove that $c_k:=\Phi[x_k^n]=(-1)^{k-1}\binom{n}{k-1}$. Induction in $n$. Base is straightforward. Induction step. We have $c_0+\dots+c_n=\Phi(x_1^n+\dots+x_{n+1}^n)=0$, by observation in 1). Next, $$ c_k-c_{k+1}=\Phi((x_k-x_{k+1})(x_k^{n-1}+\dots+x_{k+1}^{n-1})= (-1)^{k-1}\binom{n+1}k $$ by 2) and by the induction assumption. We obtain $n+1$ linear relations on $c_1,\dots,c_{n+1}$ which determine them uniquely and also the numbers $c_i=(-1)^{i-1}\binom{n}{i-1}$ satisfy these relations. This finishes the induction step.

Now we want to calculate $\Phi[(x_1+\dots+x_{k+1})^n]$. By 3) we have $$ \Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n+x_k^n-x_{k+1}^n]=0, $$ thus $$\Phi[(x_1+\dots+x_{k+1})^n-(x_1+\dots+x_{k}+x_k)^n]=(-1)^{k}\binom{n+1}k.$$ Next, $$\Phi[(x_1+\dots+x_{k-1}+2x_k)^n-(x_1+\dots+x_{k-2}+3x_{k-1})^n]=(-1)^{k-1}2^n\binom{n+1}{k-1}.$$ Proceeding in this way and summing up we get the standard formula for Eulerian number (1) on this MathWorld page.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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