Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice

2012-07-17T02:20:08Z

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 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$?

Answer by Joseph O'Rourke for Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice

2012-07-17T16:49:17Z

Here is a little data (not an answer) for small arrays for anyone who wants to compare against a theoretical calculation. I looked at square $n \times n$ arrays, $k=2$ colors only. Here are the counts for $P$, after $100$ random trials: $$ (2, 2.4), (3, 24.2), (4, 95.5), (5, 260.3), (6, 575.0), (7, 1100.1), (8, 1919.0) $$ In other words, just to interpret the last piece of data: In random $8 \times 8$ arrays, of the $\binom{64}{2}=2016$ pairs, there were on average $T=97.0$ distinct distance/color pairs (using Gerhard's definition for types $T$), leaving $P=1919.0$ repeated pairs; note $T+P=2016$. (In one trial, the distance $\sqrt{65}$ and colors $(2,2)$ occurred only once, whereas the distance $\sqrt{41}$ and colors $(1,2)$ occurred $25$ times.) Here is a graph of the same data:

Added. Now that the OP has indicated an interest in variation with the number of colors $k$, here is the same type of data, but for $k=2,3,4,5,6$:

Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice - MathOverflow

Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice

Answer by Joseph O'Rourke for Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice