Let $A(m,n)$ denote the Eulerian numbers. I'm looking for a simple combinatorial proof of the following fact.

Fact. If $p$ is prime and $0\le k < p-1$, then $A(p-1,k) \equiv 1 \pmod{p}$.

The closest thing I'm aware of is an argument of S. Tanimoto, An operation on permutations and its application to Eulerian numbers, European Journal of Combinatorics 22 (2001), 569–576 that can be adapted to give a rather complicated proof, but I'm hoping for something simpler and more direct.

  • 1
    $\begingroup$ And from the OEIS entry A008292: If n is an odd prime, then all numbers of the (n-2)-th and (n-1)-th rows are in the progression k*n+1. - Vladimir Shevelev, Jul 01 2011 $\endgroup$ – Tom Copeland Aug 3 '16 at 21:49

We identify the permutations of $1,2,\dots,p-1$ and the cyclic permutations $c=(c_0,\dots,c_{p-1})$ of $0,\dots,p-1$: if $c_k=0$, $c$ corresponds to $\pi(c):=(c_{k+1},c_{k+2},\dots,c_{k-1})$. There are $p-1$ cyclic permutations which are arithmetic progressions $(0,a,2a,\dots,(p-1)a)$, and other cyclic permutations are partitioned onto orbits of size $p$ of the action of $\mathbb{Z}_p$: $(c_0+a,c_1+a,\dots,c_{p-1}+a)$. The key fact is that in each group $C$ the corresponding permutations $\pi(c)$, $c\in C$, have the same number of ascents (example: for a cyclic permutation $01324$ the orbit contains also $12430$, $23041$, $34102$, $40213$, and permutations of $1234$ which are $1324$, $1243$, $4123$, $2341$, $2134$, all have 2 ascents.) The result follows after we also establish that the arithmetic progression $(a,2a,\dots,(p-1)a)$ (multiplication is taken modulo $p$) has exactly $p-1-a$ ascents.


You can use the closed-form expression from Wikipedia:

$$A(n,m)=\sum_{k=0}^{m+1} (-1)^k\dbinom{n+1}{k}(m+1-k)^n$$

At $k=0$ the binomial is $1$, and Fermat Little Theorem tells us the last expression is $1\pmod{p}$. All the other binomials are divisible by $n+1=p$.

  • 5
    $\begingroup$ I don't consider this to be a combinatorial proof. $\endgroup$ – Timothy Chow Aug 4 '16 at 2:47

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.