17. (FRG 3) In a permutation $\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ of the set $1,2, \ldots, n$ we call a pair $\left(x_{i}, x_{j}\right)$ discondont if $ix_{j}$. Let $d(n, k)$ be the number of such permutations with exactly $k$ discordant pairs. Find $d(n, 2)$ and $d(\mathrm{n}, 3)$.
17. For any $m=0,1, \ldots, n-1$, we shall find the number of permutations $\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ with exactly $k$ discordant pairs such that $x_{n}=n-m$. This $x_{n}$ is a member of exactly $m$ discordant pairs, and hence the permutation $\left(x_{1}, \ldots, x_{n-1}\right.$ of the set $\{1,2, \ldots, n\} \backslash\{m\}$ must have exactly $k-m$ discordant pairs: there are $d(n-1, k-m)$ such permutations. Therefore
$$
\begin{aligned}
d(n, k) & =d(n-1, k)+d(n-1, k-1) \cdots+d(n-1, k-n+1) \\
& =d(n-1, k)+d(n, k-1)
\end{aligned}
$$
(note that $d(n, k)$ is 0 if $k\binom{n}{2}$ ).
We now proceed to calculate $d(n, 2)$ and $d(n, 3)$. Trivially, $d(n, 0)=1$. It follows that $d(n, 1)=d(n-1,1)+d(n, 0)=d(n-1,1)+1$, which yields $d(n, 1)=d(1,1)+n-1=n-1$.
Further, $d(n, 2)=d(n-1,2)+d(n, 1)=d(n-1,2)+n-1=d(2,2)+$ $2+3+\cdots+n-1=\left(n^{2}-n-2\right) / 2$.
Finally, using the known formula $1^{2}+2^{2}+\cdots+k^{2}=k(k+1)(2 k+1) / 6$, we have $d(n, 3)=d(n-1,3)+d(n, 2)=d(n-1,3)+\left(n^{2}-n-2\right) / 2=$ $d(2,3)+\sum_{i=3}^{n}\left(n^{2}-n-2\right) / 2=\left(n^{3}-7 n+6\right) / 6$