Эта проблема может быть решена с использованием принципа включения-исключения
Если количество отдельных элементов равно s
, а количество пар из двух элементов равно d
, то общее количество перестановокis
A0 = (s + 2 * d)! / 2^d
Теперь мы должны вычесть число перестановок, где одна пара смежна. Существует
P1 = (s+2*d-1)! / 2^(d-1)
таких перестановок для каждого удвоенного элемента и
A1 = d *(s+2*d-1)! / 2^(d-1)
таких перестановок для всех удвоенных элементов
Теперь мы должны добавить номер перестановки, где две пары смежны. Существует
P2 = (s+2*d-2)! / 2^(d-2)
таких перестановок для каждой пары удвоенных элементов и
A2 = C(d,2) * (s+2*d-2)! / 2^(d-2)
перестановок для всех возможных пар удвоенных элементов (где C(n,k)
- биномиальный коэффициент, количество комбинаций).
Продолжите эту процедуру, изменив знак, поэтому
A(k){k=1..d} = (-1)^k * C(d, k) * (s+2*d-k)! / 2^(d-k)
и суммируйте эту последовательность, чтобы получить окончательный результат
Для вашего последнего примера (s=0,d=3
):
6!/2^3 - 3*5!/2^2 + 3*4!/2 - 3! =
720/8 - 360/4 + 72/2 - 6 =
90 - 90 + 36 - 6 = 30