Одной из наиболее распространённых комбинаторных формул является формула числа сочетаний. Для упрощения подсчётов и для доказательства некоторых утверждений удобно использовать следующие свойства сочетаний:
1. .
2. .
Доказательство:
1) .
2) .
Сочетания можно встретить и в школьном курсе математики. Например, в качестве коэффициентов бинома Ньютона выступают именно сочетания. Формула бинома Ньютона в общем виде и её доказательство приводятся в следующей теореме.
Теорема 1: .
Доказательство: Применим индукцию по .
При : .
Пусть формула верна, для случая, когда . В этом случае следующее равенство будем считать выполненным:
.
Покажем, что формула выполняется для - й степени:
.
В доказательстве можно также использовать свойство: .
Следствие: Рассмотрим некоторые частные случаи формулы бинома Ньютона:
1) если , то .
2) если , то .