Формула для количества пар неупорядоченных, полученных из уникальных элементов в k группах, исключая пары элементов из той же группы k

Question

Я не знаю, как решить следующую задачу, потому что комбинаторика не является моей сильной стороной: у меня есть несколько групп k, каждая из которых имеет хотя бы один элемент. Все элементы отличаются друг от друга. Я хочу знать общее количество неупорядоченных пар (т.е. размера 2) всех элементов из всех групп. НО я не хочу включать в это число те пары, которые возникают в результате объединения элементов, принадлежащих к одной группе k. Я ищу правильную терминологию для описания и правильную формулу для решения подобных проблем. Два примера ниже иллюстрируют проблему и желаемый результат. Ваша помощь приветствуется!

Например, группа 1 состоит из элементов a и b, группа 2 из элемента c, группа 3 из элемента d. Требуемые неупорядоченные пары: (a, c), (a, d), (b, c), (b, d), (c, d). Er go, пар 5. Исключенная пара - это пара (a, b), поскольку оба элемента принадлежат одной группе.

Другой пример: группа 1 включает a, b; 2 группа включает c, д. Требуемые пары: (a, c), (a, d), (b, c), (b, d). Общее количество пар - 4. Пары (a, b) и (c, d) исключаются, потому что соответствующие элементы принадлежат одной группе.

Спасибо!

Answer 1

У вас есть группы G (1) .. G (K), где G (k) имеет N (k) элементов. Таким образом, у вас есть

M = N(1) + .. + N(K) 

элементов всего, и вы можете сформировать

(M*(M-1))/2 

2 подмножества элементов. Но это включает и те, которые вам не нужны, которые содержат элементы из той же группы. Таких подмножеств из группы k имеется

(N(k)*(N(k)-1))/2 

. Итак, количество подмножеств, которое вы хотите, составляет

(M*(M-1))/2 - Sum{ k | (N(k)*(N(k)-1))/2}