Return to Revisions

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" 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$.