I'm interested in fixing $k$ and finding a formula, $M_k(n)$, for the number of permutations $\pi \in S_n$ such that $\operatorname{maj}(\pi) = k$, where $\mathrm{maj} \colon S_n \rightarrow \mathbb N_{\geq0}$ denotes the major index of the permutation. (It does not change the question if you replace the major index with the inversion number or any other Mahonian statistic.)
Table
Here's the table of values, given by OEIS sequence A008302, where $T(n,k) = M_k(n)$:
n\k| 0 1 2 3 4 5 6 7 8
---+------------------------------------------------------
1 | 1
2 | 1, 1
3 | 1, 2, 2, 1
4 | 1, 3, 5, 6, 5, 3, 1
5 | 1, 4, 9, 15, 20, 22, 20, 15, 9, ...
6 | 1, 5, 14, 29, 49, 71, 90, 101, 101, ...
7 | 1, 6, 20, 49, 98, 169, 259, 359, 455, ...
8 | 1, 7, 27, 76, 174, 343, 602, 961, 1415, ...
9 | 1, 8, 35, 111, 285, 628, 1230, 2191, 3606, ...
10 | 1, 9, 44, 155, 440, 1068, 2298, 4489, 8095, ...
11 | 1, 10, 54, 209, 649, 1717, 4015, 8504, 16599, ...
The table satisfies the following recurrence $$\begin{align} T(1, 0) &= 1, \\ T(n, k) &= 0 \text { for } n < 0, k < 0 \text{ or } k > \frac{n(n-1)}{2}, \\ T(n, k) &= \sum_{j=0}^{n-1} T(n-1, k-j), \text{ or alternatively}, \\ T(n, k) &= T(n, k-1) + T(n-1, k) - T(n-1, k-n). \end{align}$$
Conjecture
It appears that for $n \geq k$, the $k$-th column satisfies:
- $M_0(n) = 1$.
- $M_1(n) = -1 + n$.
- $\displaystyle M_2(n) = \frac{-2 - n + n^2}{2!}$.
- $\displaystyle M_3(n) = \frac{-7 n + n^3}{3!}$.
- $\displaystyle M_4(n) = \frac{-14 n - 13 n^2 + 2 n^3 + n^4}{4!}$.
- $\displaystyle M_5(n) = \frac{120 - 46 n - 65 n^2 - 15 n^3 + 5 n^4 + n^5}{5!}$.
- $\displaystyle M_6(n) = \frac{516 n - 356 n^2 - 165 n^3 - 5 n^4 + 9 n^5 + n^6}{6!}$.
I'm curious to know more about these in approximately the following order:
- Is it true that the $k$-th column, $M_k(n)$, always satisfies a degree $k$ polynomial for $n \geq k$?
- Is the constant part of $M_k(n)$ nonzero if and only if $n$ is a generalized pentagonal number?
- If so, is the coefficient of $x^k$ is always $\displaystyle \frac{1}{k!}$?
- Is the coefficient of $x^{k-1}$ always $\displaystyle \frac{-3n + n^2}{2k!}$?
- Is the coefficient of $x^{k-2}$ always $\displaystyle \frac{-2n + 21n^2 - 22n^3 + 3n^4}{24k!}$?
- Is the coefficient of $x^{k-m}$ always a polynomial of degree $2m$?
- Is the coefficient of $x^{k-m}$ given by a polynomial whose numerator is divisible by $\displaystyle \prod_{i=0}^{m-1} (x-i)$?
- Do these polynomials $M_k(n)$ have a combinatorial explanation in terms of (finite) exponential generating functions?
The generating function for the inversion numbers is well known: $$ T_{n,k}=[q^k]\frac{(1-q)(1-q^2)\cdots(1-q^{n})}{(1-q)^n} $$ We can safely remove the factors of $(1-q^{k+1})(1-q^{k+2})\cdots(1-q^n)$ from the numerator without changing the $q^k$ coefficient, so $$ T_{n,k}=[q^k](1-q)(1-q^2)\cdots(1-q^k)(1-q)^{-n} $$ By the pentagonal number theorem, $$(1-q)(1-q^2)(1-q^3)\cdots=\sum_{j\in \mathbb Z}(-1)^jq^{j(3j-1)/2}.\tag{*}$$ For this purpose, we only need the power of $q$ up to $q^k$ in $(1-q)(1-q^2)\cdots(1-q^k)$, which indeed agree with the terms of $q^k$ up to $k$ in $(*)$. Finally, $[q^i](1-q)^{-n}= \binom{n+i-1}{i}$. Therefore, $$ \begin{align} T_{n,k} &=[q^k]\left(\sum_{j\in \mathbb Z}(-1)^jq^{j(3j-1)/2}\right)\left(\sum_i q^i\binom{n+i-1}{i}\right) \\&=\sum_{j\in \mathbb Z} (-1)^j\binom{n+k-j(3j-1)/2-1}{k-j(3j-1)/2} \end{align} $$ Even though this is an infinite sum, there are only finitely many $j$ for which the lower index $k-j(3j-1)/2$ is nonnegative, and only those contribute positively. This explains your observation about the pentagonal numbers.
Each binomial coefficient can be expanded into a polynomial in $n$, but I do not know how to find the coefficients of that nicely. I think the above expansion is quite pretty, since this shows that $T_{n,k}$ is a linear combination of $O(\sqrt{k})$ binomial coefficients, instead of $O(k)$ powers of $n$.