0
$\begingroup$

This is stated in many places but seldom proved. The goal is to prove that, for fixed $m\geq 0$, $$\lim_{n\rightarrow\infty}A(n,m)\sim (m+1)^n$$ where $A(n,m)$ are the Eulerian Numbers, namely, the number of permutations of $\{1,2,\ldots,n\}$ with exactly $k$ "ascents" (places where the element is greater than the previous one).

$\endgroup$
0
$\begingroup$

Let us prove that $$\lim_{n\rightarrow\infty}\frac{A(n,m)}{(m+1)^n}=1.$$ We use the formula for the Eulerian Numbers provided in the book Concrete Mathematics: $$A(n,m)=\sum_{k=0}^m\binom{n+1}{k}(m+1-k)^n(-1)^k.$$ Dividing the equation above by $(m+1)^n$ we have: \begin{eqnarray} \frac{A(n,m)}{(m+1)^n}&=& \sum_{k=0}^m\binom{n+1}{k}\frac{(m+1-k)^n}{(m+1)^n}(-1)^k\\ &=& \sum_{k=0}^m\binom{n+1}{k}\left(\frac{m+1-k}{m+1}\right)^n(-1)^k\\ &=& \sum_{k=0}^m\binom{n+1}{k}\left(1-\frac{k}{m+1}\right)^n(-1)^k\\ %&=& %1+\sum_{k=1}^m\binom{n+1}{k}\left(1-\frac{k}{m+1}\right)^n(-1)^k\\ \end{eqnarray} Let $a_{n,k}:=\binom{n+1}{k}\left(1-\frac{k}{m+1}\right)^n(-1)^k$, thus $\frac{A(n,m)}{(m+1)^n}=\sum_{k=0}^ma_{n,k}$. If $k=0$ then $a_{n,k}=1$. We are going to prove that, when $k\neq 0$, $a_{n,k}\rightarrow 0$.

Consider the series $\sum_{n=0}^\infty a_{n,k}$. We will prove that this series converges if $k\neq 0$ using the ratio test: $$\left|\frac{a_{n+1,k}}{a_{n,k}}\right|= \frac{\binom{n+2}{k}\left(1-\frac{k}{m+1}\right)^{n+1}(-1)^k} {\binom{n+1}{k}\left(1-\frac{k}{m+1}\right)^n(-1)^k}= \frac{n+2}{n+2-k}\left(1-\frac{k}{m+1}\right)$$ Note that, when $n\rightarrow\infty$, $\frac{n+2}{n+2-k}\rightarrow 1$. So $\left|\frac{a_{n+1,k}}{a_{n,k}}\right|\rightarrow 1-\frac{k}{m+1}$. If $k\neq 0$ then $1-\frac{k}{m+1}<1$. Therefore, by the ratio test, the series $\sum_{n=0}^\infty a_{n,k}$ converges. It follows that $a_{n,k}\rightarrow 0$ when $n\rightarrow\infty$.

So we have $\frac{A(n,m)}{(m+1)^n}=\sum_{k=0}^ma_{n,k}$ with $a_{n,0}=1$ and $a_{n,k}\rightarrow 0$ when $k\neq 0$ and $n\rightarrow\infty$. This means that $$\lim_{n\rightarrow\infty}\frac{A(n,m)}{(m+1)^n}= \lim_{n\rightarrow\infty}\sum_{k=0}^ma_{n,k}=1 %\lim_{n\rightarrow\infty}1+\sum_{k=1}^m\lim_{n\rightarrow\infty}a_{n,k}= %1+\sum_{k=1}^ma_{n,k}= $$

$\endgroup$

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.