1
$\begingroup$

Let $[n] := \{1,2,\dots,n\}$. An Eulerian number, $A(n,k)$, denotes the number of permutations $\sigma \in S_n$ of $[n]$ such that exactly $k$ numbers have the property that $\sigma(i) < \sigma(i+1)$.

It is known that $\sum_{k=0}^{n-1}A(n,k) = n!$

Question: Do there exist results about the expected number of permutations $\sigma \in S_n$ such that exactly $k$ numbers have the property that $\sigma(i) < \sigma(i+1)$.

I.e. is there a simple identity for $\frac{\sum_{k=0}^{n-1}kA(n,k)}{n!}$. Or does there exist an asymptotic result of the form:

$$\text{ as } n \rightarrow \infty, \frac{\sum_{k=0}^{n-1}kA(n,k)}{n!} \rightarrow X $$

$\endgroup$
2
$\begingroup$

if you fix $k$ and let $n$ go to $\infty$ it is fairly clear that $\frac{A(n,k)}{n!}$ i.e. the probability that exactly $k$ numbers will have desiredd property will tend to $0$. on the other hand if you reverse your inequality you get a dual property. clearly its expectation is the same as the one you're considering (cause the number for original permutation is equal to the dual of inversed permutation and every permutation has its unique inverse, where by inverse I mean $a, b, c, d \rightarrow d, c, b, a$ - writing it down in reverse order). moreover for each permutation those two numbers add up to $n-1$ so the expectation of each of them is $(n-1)/2$. is this what you're asking?

a different, probably more interesting / complicated question would be to find the limit of $\frac{A(n,k(n))}{n!}$ where $k(n)$ is some specified function

$\endgroup$
1
$\begingroup$

As mm-aops pointed out, $$ \frac{\sum_{k=0}^{n-1}kA(n,k)}{n!} = \frac{n-1}{2} \implies \lim_{n\rightarrow \infty} \frac{\sum_{k=0}^{n-1}kA(n,k)}{n!} = \infty $$ due to the symmetry of the permutations in $S_n$. Observe what is happening for small $n$ in this table:

1: [1] 0.0
2: [1, 1] 0.5
3: [1, 4, 1] 1.0
4: [1, 11, 11, 1] 1.5
5: [1, 26, 66, 26, 1] 2.0
6: [1, 57, 302, 302, 57, 1] 2.5
7: [1, 120, 1191, 2416, 1191, 120, 1] 3.0
8: [1, 247, 4293, 15619, 15619, 4293, 247, 1] 3.5
9: [1, 502, 14608, 88234, 156190, 88234, 14608, 502, 1] 4.0
$\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.