8
$\begingroup$

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.

$\endgroup$
1
  • 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$ Aug 3, 2016 at 21:49

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • 5
    $\begingroup$ I don't consider this to be a combinatorial proof. $\endgroup$ Aug 4, 2016 at 2:47

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.