Imagine I have an $N$ by $M$ rectangular lattice where I randomly assign one of $k$ colors to every vertex in the lattice. I then write down a list of the ${N*M}\choose{2}$ possible unordered pairs of vertices, noting the color of each vertex in a pair and the Euclidean distance between them. Finally, I count the number of pairs of vertices with the both the same vertex color combination and Euclidean distance as a previously recorded pair, $P$. For example, if I've previously recorded a "red" and a "blue" vertex with Euclidean distance $d_i$ between them, which we'll write as a tuple: {$c_1, c_2, d_i$}, another example of a "red" and "blue" vertex pairing with the same Euclidean distance, {$c_1,c_2,d_i$} or {$c_2,c_1,d_i$} (order of the colors does not matter), would increase $P$ by one.
With a hat tip to Gerhard Paseman, we can write that $P = $${N*M}\choose{2}$$-T$, where $T$ is the total number of distinct tuples: {$c_i,c_j,d_k$}, where , again, the order of the colors do not matter and vertices of the same color are allowed.
As a function of $N$, $M$, and $k$, what is the expected value of $P$?
