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.