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 identity 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]: http://www.springerlink.com/content/m36k5q2741233625/