Вычисление количества сочетаний

Число 10 на математических часах представляется как
$10=C_5^2$

Эта запись означает количество сочетаний из 5 элементов по 2. Иными словами, сколькими способами можно выбрать из пяти различных предметов неупорядоченную пару

Искомое число можно подсчитать непосредственно. Из (1,2,3,4,5) можно выбрать такие пары (не забываем, что порядок в них неважен):

(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)
Всего их 10.

Как же вычислять $C_n^m$ не прибегая к непосредственному перечислению? Первый предмет можно выбрать n способами. Второй предмет можно выбрать (n-1) способами. Для третьего будет (n-2) способов, и т.д. до (n-m+1) способов выбрать m-й предмет.

Значит, количество способов выбрать m предметов из n при условии, что порядок важен, равно произведению $n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1)$.

Сами же эти m предметов можно переставить между собой m! способами. Значит, каждая непорядоченная группа из m предметов при нашем подсчёте оказалась подсчитанной m! раз.

Поэтому $C_n^m$ оказывается равно дроби: $\frac{n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1)}{m!}$

Эту формулу можно упростить, заметив, что $n\cdot(n-1)\cdot(n-2)\cdot\dots\cdot(n-m+1) = \frac{n!}{(n-m)!}$

Таким образом, $C_n^m = \frac{n!}{m!(n-m)!}$