Eulerian Number Asymptotics

235 Views Asked by At

The Eulerian Number $A(n,k)$ is the number of permutations of $1$ to $n$ with exactly $k$ rises (or ascents, i.e., positions $i$ such that $x_i<x_{i+1}$).

The article The Boundary of the Eulerian Number Triangle by Alexander Gnedin and Grigori Olshanski, presents the following asymptotic relation (Remark 12):

$$\lim_{n\rightarrow\infty} A(n,k)\sim (k+1)^n\qquad \text{for fixed $k=0,1,\ldots$}$$

According to them:

The relation can be readily checked directly. For instance, it follows from formula $$A(n,k)=\sum_{j=0}^k(-1)^j\binom{n+1}{j}(k+1-j)^n$$

I'm not an expert on asymptotic theory so I don't know if this is straightforward or not. Should I really compute the ratio $$\frac{A(n,k)}{(k+1)^n}=\frac{\sum_{j=0}^k(-1)^j\binom{n+1}{j}(k+1-j)^n}{(k+1)^n}$$ and manually prove that it converges to $1$? Or are there techniques to approach these kind of problems? I see some properties regarding products, quotients and powers... but the Eulerian Number formula is a sum, and sum does not behave well with asymptotics

1

There are 1 best solutions below

4
On BEST ANSWER

The result follows from $$\lim_{n\to \infty}\binom {n+1}{j}\frac {(k+1-j)^n}{(k+1)^n}=\delta_{0j}.$$

Note that$$\binom {n+1}{j}\le \frac {(n+1)^j}{j!},$$ and $$\lim_{n\to\infty} (n+1)^j a^n=0$$ for $|a|<1$ and any fixed $j$.