Задача № 29. Вычислить число сочетаний из n по k

Формулировка. Даны натуральные числа n и k (k не превышает n). Вычислить число сочетаний из n по k.

Примечание: в комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов; при этом наборы, отличающиеся только порядком следования элементов, считаются одинаковыми. Обозначение числа сочетаний из n по k элементов: . При этом считается, что , и для любого натурального n.

Например, найдем все 2-элементные сочетания 3-элементного множества {1, 2, 3}. Таковыми являются {1, 2}, {1, 3} и {2, 3}. То есть, таковых сочетаний 3. При этом, например, {1, 2} и {2, 1} – одинаковые сочетания, так как они отличаются только порядком следования элементов.

Решение. Из комбинаторики известна формула:

Не интересуясь вопросом ее вывода и корректности, мы будем использовать тот ее вариант, который написан после второго знака равенства (если смотреть слева направо), так как он наиболее оптимален для вычислений и позволит обойтись двумя циклами (для числителя for с downto, для знаменателя – просто for). Для числителя и знаменателя предусмотрим соответственно переменные num (от англ. numerator – «числитель») и denom (от англ. denominator – «знаменатель»), которым нужно поначалу присвоить значения 1, чтобы осуществить контроль частных случаев (этот вопрос упомянут в предыдущей задаче):

1) При k = 0 переменная num останется неизменной и будет равна 1, так как невозможен вход в цикл с уменьшением от n до (n + 1), переменная denom будет равна 1 как 0!;

2) При n = k num и denom будут вычислены и при делении дадут единицу;

3) При n = k = 0 переменная denom будет вычислена как 0!, а переменная num не изменится по невозможности входа в цикл с уменьшением от 0 до 1.

Код: