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$:
2 Revised according to clarification of $P$.; added 15 characters in body
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 mean counts , for $P$, after $100$ random trials, of the average number of pair/color counts, which I interpret as $P$ in the original question: $$(2, 1.80)2.4), \; (3, 3.01)24.2), \; (4, 4.95)95.5), \; (5, 7.55)260.3), \; (6, 11.48)575.0), \; (7, 15.49)1100.1), \; (8, 20.831919.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, the there were on average number of repeats of the same distance and the same two colors is $20.83$. 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: 1 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 mean counts, after$100$random trials, of the average number of pair/color counts, which I interpret as$P$in the original question: $$(2, 1.80), \; (3, 3.01), \; (4, 4.95), \; (5, 7.55), \; (6, 11.48), \; (7, 15.49), \; (8, 20.83)$$ In other words, just to interpret the last piece of data: In random$8 \times 8$arrays, of the$\binom{64}{2}=2016$pairs, the average number of repeats of the same distance and the same two colors is$20.83$. (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: