Average number of inversions in an involution I'm working through some exercises in Sedgewick's Analysis of Algorithms, but I'm stuck on 7.45:

Find the CGF for the total number of inversions in all involutions of length $N$. Use this to find the average number of inversions in an involution.

I understand that the construction for $\mathrm{inversions}(i)$ will look different than say the construction of $\mathrm{inversions}(p)$ for a random permutation, since we create fewer than $|i|+1$ involutions upon adding the next element. That next element cannot be put in a place where it will cause a 2-cycle to become a 3-cycle. As such, the number of inversions caused by $|i|+1$ will be fewer than the construction for inversions in a random permutation. This depends on how many 2-cycles exist within the $|i|$ involution. I have no idea how it should look.
 A: Here's a recurrence relation governing the number of inversions in all involutions of length $n$. 
Let $a_n$ be the number of involutions of length $n$ and $c_n$ be the number of inversions in all involutions of length $n$. Let's construct the recurrence relation governing $a_n$ which will help constructing the same for $c_n$. 
Imagine we start with the set of integers ${1,2,3...N}$ for which we are considering all involutions. I will denote the integers with uppercase letters and the corresponding starting location with lowercase letters. Now we have two ways of constructing a self-inverse mapping. 
$\textbf{Case 1}$ : We map the integer $N$ to itself at location $n$ and then number of involutions 
with rest of the integers is $a_{n-1}$. Thus number of such self-inverse mapping is $a_{n-1}$
$\textbf{Case 2}$: We map the integer $N$ to the location $i$ and integer $I$ to the location $n$ and then number of involutions with rest of the integers is $a_{n-2}$ as no other self-inverse mapping can involve the integers at location $i,n$. We have $(n-1)$ choice of such location $i$, thus total number of such self-inverse mapping is $(n-1)a_{n-2}$.
So we have the recurrence relation governing $a_n$ as, 
$a_n = a_{n-1} + (n-1)a_{n-2}$
with $a_0 = a_1 = 1$
Alse see http://mathworld.wolfram.com/PermutationInvolution.html
Now let's tackle the number of inversions in each of the two cases mentioned above.
$\textbf{Case 1}$: In this case where we map the integer $N$ to itself at location $n$, there is no inversion pair with $N$ as an entry and thus total number of inversions in this case is $c_{n-1}$
$\textbf{Case 2}$: This is a more interesting case. Note that when we map the integer $N$ with the integer $I$, there are exactly $(n-i)$ integers which are to the right of location $i$ and less than the integer $N$ and by symmetry $(n-i)$ integers which are to the left of location $n$ and greater than the integer $I$. 
For example for $n = 6, i=3$, 
starting set $T = (1,2,3,4,5,6)$
mapped set $T'=(1,2,\mathbf{6},4,5,\mathbf{3})$
Note that exactly $(6-3)=3$ integers($4,5,3$) are to the right of location $3$ and less than the integer at location $i=3$ which is $N=6$ and exactly $3$ integers ($6,4,5$) are to the left of location $6$ and greater than the integer at location $n=6$ which is $I=3$.
Number of inversions with either $N$ or $I$ as an entry would then be equal to $2(n-i)-1$. We need to subtract $1$ as we have counted the inversion $(N,I)$ twice. Let's call such an inversion pair $inv(N \cup I)$
$\textbf{Here's the most important piece of the recurrence relation}$: number of such involutions with the inversion pair $inv(N \cup I)$ is $a_{n-2}$. This is somewhat similar logic used to derive the recurrence relation of $a_n$. 
Going back to the example, another valid involution can be,
$T'' = (1,4,\textbf{6},2,5,\textbf{3})$
Note that $T''$ also has $2(n-i)-1$ number of inversions which are of type $inv(N \cup I)$.
Now we need to consider additional inversions which doesn't have any of $I$ or $N$ in it. For example in the case of $T''$, $(4,2)$ is a legitimate inversion. Total number of such inversions is simply $c_{n-2}$ (for the case where we have the map $n \leftrightarrow i$)
So what is the total number of inversions in Case 2? There are $(n-1)$ possible choice for $i$ and thus the total number of inversions is $\sum_{i=1}^{n-1} \left[(2(n-i)-1)a_{n-2} + c_{n-2}\right] = (n-1)^2a_{n-2} + (n-1)c_{n-2}$ 
So the recurrence relation governing $c_n$ becomes, 
$c_n = c_{n-1} + (n-1)c_{n-2} + (n-1)^2a_{n-2}$
with $c_1 = 0, c_2 = 1$
I calculated upto $c_6$ manually which matches with https://oeis.org/A211606. You can try writing a program to check further numbers down the sequence and share the results.
