0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Sorry maybe I wasn't clear. The limit of the quotient $\frac{A(n,k)}{(k+1)^n}$ should be $1$ instead of $0$ when $n$ goes to infinity ($k$ is fixed) $\endgroup$ – user449031 Mar 30 '18 at 22:46
  • $\begingroup$ $\lim n^k a^n=0$ for any fixed $k $ as well. Therefore only the term $(k+1)^n $ survives. $\endgroup$ – user Mar 30 '18 at 22:53
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Oh my god thank you! That was really easier than I was attempting to do. It didn't went through my mind to put the binomial $\leq$ something else... I was just expanding them 😓 $\endgroup$ – user449031 Mar 31 '18 at 14:35
  • 1
    $\begingroup$ @aaa In fact one can proceed directly with binomial by ratio test as $\frac{a_n}{a_{n-1}}=\frac{n+1}{n+1-j}\left (1- \frac{j}{k+1}\right)$. $\endgroup$ – user Apr 2 '18 at 3:30
  • $\begingroup$ In this case when $n\rightarrow\infty$ then $\frac{a_n}{a_{n-1}}\rightarrow 1-\frac{j}{k+1}$ $\endgroup$ – user449031 Apr 12 '18 at 18:43
  • 1
    $\begingroup$ @user exactly. Therefore $a_n\rightarrow 0$ if $j\ne0$. $\endgroup$ – user Apr 12 '18 at 18:50

Your Answer

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