Сколькими способами можно разбить 14 человек на пары

Интересная задачка сегодня встретилась в ВК.
Сколькими способами можно 14 человек разбить на пары?

По инерции, зная формулу числа сочетаний $C_n^m$, может показаться, её нужно применить и здесь. Однако $C_{14}^2=\frac{14\cdot 13}{2}=91$ даст только число способов, которыми можно выбрать одну пару из 14ти человек.

Более того, давайте рассмотрим случай разбивки на пары группы из 4х человек. Это можно сделать тремя способами (ведь неважно, в каком порядке эти пары идут):
(1,2) и (3,4);
(1,3) и (2,4);
(1,4) и (2,3).
Формула же $C_4^2$ даёт результат 6.

Вообще, задачи по комбинаторике лучше решать рассуждением, а не механическим применением формул, (как это часто требуют в школах). Пусть у нас есть 2n человек (ведь при нечётном их количестве пары не соберутся), перенумерованные от 1 до 2n. Сформируем первую пару, взяв первого человека и какого-нибудь ещё. Сколькими способами можно это сделать? Для выбора пары первому человеку существует (2n-1) вариантов.


Первая пара вышла, теперь берём человека с наименьшим номером из оставшихся и ищем ему пару. Для этого остаётся уже (2n-3) вариантов. Поступая аналогично, видим, что для выбора 3-й пары будет (2n-5), четвёртой -  (2n-7) способов, и так далее.

Наконец, n-ю пару можно будет выбрать (2n-(2n-1)) = 1, то есть одним способом (это понятно, т.к. они остаются последними в группе, после того, как все вышли).

Значит, всего способов будет (2n-1)*(2n-3)*...*5*3*1. Надо ли полученный результат ещё на что-то делить (как мы делаем обычно, когда оказывается, что предложенный способ подсчёта учёл некоторые случаи дважды)?. Нет, так как при таком способе формирования пар номера первых людей в парах и номера людей внутри пар только возрастают и поэтому повторов не будет.

Для n=7 (т.е. для 14-ти человек) формула даст 13*11*9*7*5*3*1 = 135135 способов.

Для n=3 (т.е. для 6-ти человек) формула даст 5*3*1 = 15 способов. Вот они все:
(1,2), (3,4)  и (5,6);
(1,2), (3,5)  и (4,6);
(1,2), (3,6)  и (4,5);

(1,3), (2,4)  и (5,6);
(1,3), (2,5)  и (4,6);
(1,3), (2,6)  и (4,5);

(1,4), (2,3)  и (5,6);
(1,4), (2,5)  и (3,6);
(1,4), (2,6)  и (3,5);

(1,5), (2,3)  и (4,6);
(1,5), (2,4)  и (5,6);
(1,5), (2,6)  и (4,5);

(1,6), (2,3)  и (4,5);
(1,6), (2,4)  и (3,5);
(1,6), (2,5)  и (3,4).

Вообще-то, задачу можно было решить и применением стандартной формулы $C_n^m$.
Чтобы выбрать пару среди 2n человек у нас есть $C_{2n}^2=\frac{2n(2n-1)}{2} = n(2n-1)$ способов.
Чтобы выбрать пару среди оставшихся 2n-2 человек у нас есть $C_{2n}^2=\frac{(2n-2)(2n-3)}{2}=(n-1)(2n-3)$ способов.
Чтобы выбрать пару среди оставшихся 2n-2 человек у нас есть $C_{2n}^2=\frac{(2n-2)(2n-3)}{2}=(n-2)(2n-5)$ способов.
.....
Чтобы выбрать пару среди оставшихся 4 человек у нас есть $C_{4}^2=2\cdot 3$ способов.
Чтобы выбрать пару среди оставшихся 2 человек у нас есть $C_{2}^2=1\cdot 1$ способ.

Перемножив эти величины, получим

$C_{2n}^2\cdotC_{2n-2}^2\cdotC_{2n-4}^2\cdot\dots\C_{4}^2\cdotC_{2}^2=$

$= n(2n-1)(n-1)(2n-3)(n-2)(2n-5)\dots\cdot 2\cdot 3\cdot1\cdot1$

Вот этот результат нужно делить на количество переставновок из n элементов, то есть на n! В итоге получаем тот же самый ответ, что и ранее.