Consider a permutation $\sigma$ of $[1..n]$. An inversion is defined as a pair $(i, j)$ of indices such that $i < j$ and $\sigma(i) > \sigma(j)$.
Define $A_k$ to be the number of permutations of $[1..n]$ with at most $k$ inversions.
Question: What's the tight asymptotic bound for $A_k$?
A related question was asked before: Number of permutations which have the same Kendall-Tau distance
But the question above was regarding computing $A_k$. It can be computed using dynamic programming, since it satisfies the recurrence relation shown here: https://stackoverflow.com/questions/948341/dynamic-programming-number-of-ways-to-get-at-least-n-bubble-sort-swaps
The number of permutations with exactly $k$ inversions has also been studied and it can be expressed as a generating function: http://en.wikipedia.org/wiki/Permutation#Inversions
But I can't find a closed-form formula or an asymptotic bound.