We prove for $n \ge 4$. If the permutations $X_n = (x_1, x_2, \dots, x_n)$ of $1, 2, \dots, n$ consist of a set $A$, and $f(X_n) = x_1 + 2x_2 + 3x_3 + \dots + nx_n$, $M_n = \{f(X) \mid X \in A\}$, then $|M_n| = \frac{n^3 - n + 6}{6}$.

Using mathematical induction on $n$, we see that
$$M_n = \left\{ \frac{n(n+1)(n+2)}{6}, \frac{n(n+1)(n+2)}{6} + 1, \dots, \frac{n(n+1)(2n+1)}{6} \right\}$$
For $n=4$, by arranging inequality, one can see the smallest number of $M$ is $f(\{4, 3, 2, 1\}) = 20$, and the biggest number is $f(\{1, 2, 3, 4\}) = 30$. Because
$$\begin{align*} f(\{3, 4, 2, 1\}) &= 21, \quad f(\{3, 4, 1, 2\}) = 22, \\ f(\{4, 2, 1, 3\}) &= 23, \quad f(\{3, 2, 4, 1\}) = 24, \\ f(\{2, 4, 1, 3\}) &= 25, \quad f(\{1, 4, 3, 2\}) = 26, \\ f(\{1, 4, 2, 3\}) &= 27, \quad f(\{2, 1, 4, 3\}) = 28, \\ f(\{1, 2, 4, 3\}) &= 29, \end{align*}$$
we have, $|M_4| = |\{20, 21, \dots, 30\}| = 11 = \frac{4^3 - 4 + 6}{6}$.

Suppose that the statement is true for $n-1$ ($n \ge 5$). In the case of $n$, for a permutation $X_{n-1} = (x_1, x_2, \dots, x_{n-1})$ of $1, 2, \dots, n-1$, let $x_n = n$; then we get a permutation $(x_1, x_2, \dots, x_{n-1}, n)$ of $1, 2, \dots, n$, and so
$$\sum_{k=1}^{n} kx_k = n^2 + \sum_{k=1}^{n-1} kx_k.$$
According to the supposition, the value of $\sum_{k=1}^{n} kx_k$ can be every integer number in the interval
$$\left[ n^2 + \frac{(n-1)n(n+1)}{6}, n^2 + \frac{(n-1)n(2n-1)}{6} \right] = \left[ \frac{n(n^2+5)}{6}, \frac{n(n+1)(2n+1)}{6} \right].$$
Let $x_n = 1$. Then
$$\begin{aligned} \sum_{k=1}^{n} kx_k &= n + \sum_{k=1}^{n-1} kx_k \\ &= n + \sum_{k=1}^{n-1} k(x_k - 1) + \frac{n(n-1)}{2} \\ &= \frac{n(n+1)}{2} + \sum_{k=1}^{n-1} k(x_k - 1). \end{aligned}$$
According to the supposition, the value of $\sum_{k=1}^{n} kx_k$ can be every integer number in the interval
$$\left[ \frac{n(n+1)}{2} + \frac{(n-1)n(n+1)}{6}, \frac{n(n+1)}{2} + \frac{n(n-1)(2n-1)}{6} \right] = \left[ \frac{n(n+1)(n+2)}{6}, \frac{2n(n^2+2)}{6} \right].$$
Because $\frac{2n(n^2+2)}{6} \ge \frac{n(n^2+5)}{6}$, according to the supposition the value of $\sum_{k=1}^{n} kx_k$ can be every integer number in the interval
$$\left[ \frac{n(n+1)(n+2)}{6} , \frac{n(n+1)(2n+1)}{6} \right].$$
The statement is also true for $n$. Since
$$\frac{n(n+1)(2n+1)}{6} - \frac{n(n+1)(n+2)}{6} = \frac{n^3 - n + 6}{6},$$
one can see that $|M_n| = \frac{n^3 - n + 6}{6} + 1$.

In particular, $|M_9| = 121$.