Robust Coincident Rolls

You roll a fair $k$-sided die $n$ times independently. Let $M$ be the number of pairs $(i, j)$ with $1 \le i < j \le n$ such that roll $i$ equals roll $j$. Find $E[M]$.

Additional robustness twist: before observation, an independent random relabeling of outcome labels is applied. Compute the same target and justify invariance.