7
$\begingroup$

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.

$\endgroup$
13
  • $\begingroup$ What is $k$? Should it be $i$? $\endgroup$
    – Ira Gessel
    Dec 15, 2016 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$ Dec 15, 2016 at 0:19
  • $\begingroup$ My mistake—sorry. $\endgroup$
    – Ira Gessel
    Dec 15, 2016 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$ Dec 15, 2016 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$ Dec 15, 2016 at 3:34

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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