The trace of a permutation matrix is the number of fixed points of the corresponding permutation.  This is a special case of the identity proved in "[An identy for fixed points of permutations][1]" by Goldman, where the average of the $k^{th}$ powers of the number of fixed points is shown to be the $k^{th}$ Bell number $B_k$ when $k<n$.  Your case follows because $B_2=2$.


  [1]: https://doi.org/10.1007/BF01834125 "Jay R. Goldman, Aequationes Math. 13 (1975), 155-156"