Выбор. Сочетания

Выбор - это ситуация разбиения на две группы (выбранные - оставшиеся). Поэтому число способов выбрать k элементов из n равно числу разбиений n элементов на две группы по k и n-k элементов, то есть n!/ k!(n-k)!. Это число ввиду стандартности и широкой распространенности задачи выбора носит специальное название - число сочетаний из n элементов по k, и обозначается

.

Обычно для вычислений используется наряду с основной

используется также упрощенная формула (которая особенно удобна, когда k мало по сравнению с n:

Поскольку выбранные и оставшиеся с точки зрения разбиения на группы равноправны (все равно, какой список составлять, тех кого приглашать на день рождения, или наоборот, кого не приглашать – результат будет тот же – придут приглашенные), то