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" 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$.
2 of 2
fixed broken link to springerlink.com; added citation information in tooltip; "corrected" title of paper (it really does say "identy" instead of "identity")
The Amplitwist
- 1.4k
- 3
- 11
- 22
Jonas Meyer
- 7.3k
- 2
- 43
- 50